게임(BOJ1103)

문제

이미지클릭

문제 설명

• n*m직사각형의 보드판이 존재하는 데, 다음과 같은 방법을 따른다.

1. 기본적으로 가장 왼쪽 위칸, (1,1)에서 시작한다.
2. 현제 위치에 있는 숫자만큼 상하좌우로 이동가능하다. 
3. 만약 구덩이에 빠지면 게임은 종료한다. (이동하면서 만나는 구덩이는 무시한다.)
4. 만약 무한번 움직일 수 있는 경우가 존재한다면 무조건 -1을 출력해 준다.

문제 해설

• 처음에는 bfs로도 풀 수 있을 거라고 생각하였지만 몇 가지 조건으로 인해서 어려움을 겪었다.

bfs를 사용하면 방문한 점을 원복 하는 데 어려움이 존재하기 때문에 dfs, dp를 활용하여서 깊이 우선으로 탐색할 필요가 있다.

• dfs

처음 점부터 시작하여서 깊이를 기준으로 하여서 탐색해 준다.
만약 연속으로 방문하는 지점이 존재한다면 무한으로 반복된다는 것을 의미하기 때문에 그 즉시 -1을 출력하고 종료한다.

• dp

이동하는 횟수를 차례대로 체크해 주면서 탐색을 진행해 준다.
만약 dp테이블에 이미 이동한 횟수가 체크되어 있다면 이동 횟수만 return 해준다.
이를 계속 반복해 주면서 dp테이블을 채워준다.

최종코드

#include<bits/stdc++.h>
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m;
int d[54][54], dp[54][54], visited[54][54];
int dfs(int x, int y) {
    if (x <= 0 || y <= 0 || x > n || y > m || d[x][y] == 0) return -1e9; #범위 벗어나면 작은 값 return
    if (visited[x][y]) return -1; #방문처리가 되어있다면 -1 return(무한히 반복됨을 의미)
    if (dp[x][y] != -1) return dp[x][y]; #dp테이블이 체워져 있다면 그 이동횟수를 return
    visited[x][y] = 1; #처음에는 방문처리
    dp[x][y] = 1; #1로 초기화 해주기
    for (int i = 0; i < 4; i++) {
        int nx = x + d[x][y] * dx[i], ny = y + d[x][y] * dy[i];
        int result = dfs(nx, ny); 
        if (result == -1) { #-1을 return받으면 무한히 반복되는 것을 의미하기 때문에 -1출력해주고 종료
            cout << -1;
            exit(0);
        }
        dp[x][y] = max(dp[x][y], result + 1); 
        #무한 반복이 아니면 (현제 위치에서의 최대 이동횟수)와 (return 받은 이동횟수+1)중 큰 값을 저장해준다.
    }
    visited[x][y] = 0; #방문상태를 원복해준다.
    return dp[x][y]; #이동횟수의 최댓값을 return
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            if (c == 'H') d[i][j] = 0;
            else d[i][j] = c - '0';
        }
    }
    memset(dp, -1, sizeof(dp)); #-1로 dp테이블 초기화
    int ans = dfs(1, 1); #(1,1)에서 출발
    cout << ans;
}

이미지클릭