[백준 1103] 게임

A. 접근법

1. 처음에는 BFS를 통해서 구현하려고했다. 이미 방문한 곳이라면 다음 이동은 의미가 없고 무한대의 이동이 가능할 것이라고 판단했지만 이것은 틀린 방법이다.

4 4
3HH2
H1HH
H2H1
2219

의 인풋이 있을 경우 (0,0)(1) -> (0,3)(2) -> (2,3)(3) -> (3,3)(4) 이 루트가 (3,3)을 먼저 방문하면 (0,0)(1) -> (3,0)(2) -> (3,2)(3) -> (3,3)(4)이 될 때 다른 루트임에도 무한대의 이동이 가능하다고 판단한다.

2. 단순 DFS통해서 구현했을 때는 시간초과가 발생했다. 단순 DFS로 구현했을 때는 칸에 도달할 때 마다 계산을 진행하므로 비효율적이다.

3. DFS + DP : DFS로 구현하되 방문한 칸의 값을 저장하는 배열을 선언하여 칸에 방문했을 때 해당 칸의 값이 계산이 되어 있다면 추가적인 계산을 생략하고 그 값을 사용한다.

B. 구현

if(visit[nx][ny]) {
dp[x][y] = -1;
return dp[x][y];
}

DFS탐색 도중 다음 방문예정인 칸이 이미 방문했다면 무한이 이동가능하기 때문에 dp배열에 -1을 넣는다.

for(int i = 0; i < 4; i++) {
if(tmp[i] == -1) {
dp[x][y] = -1;
return dp[x][y];
}
if(tmp[i] > mx)
mx = tmp[i];
}
dp[x][y] = mx + 1;
return dp[x][y];

tmp 벡터는 상하좌우의 이동가능한 값을 저장하고 있는 변수인데, 이 중 하나라도 -1이면 무한이 이동이 가능하다라는 의미이기 때문에 해당 dp배열에도 -1을 넣고 이 값을 반환한다.

그 외의 경우에는 상하좌우 값 중 최대 값을 구해 자기 자신을 포함하는 1의 값을 더해 dp배열에 저장 후 해당 값을 반환한다.

C. 코드

#include<iostream>
#include<vector>

using namespace std;
int N, M;
vector<string> table;
bool visit[50][50];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int dp[50][50];
int dfs(int x, int y) {
    if(dp[x][y] != 0)
        return dp[x][y];

    vector<int> tmp(4,0);

    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i] * (table[x][y] - '0');
        int ny = y + dy[i] * (table[x][y] - '0');

        if(nx >= 0 && nx < N && ny >= 0 && ny < M && table[nx][ny] != 'H') {
            if(visit[nx][ny]) {
                dp[x][y] = -1;
                return dp[x][y];
            }

            else {
                visit[nx][ny] = true;
                tmp[i] = dfs(nx, ny);
                visit[nx][ny] = false;
            }
        }
    }

    int mx = 0;
    for(int i = 0; i < 4; i++) {
        if(tmp[i] == -1) {
            dp[x][y] = -1;
            return dp[x][y];
        }
        if(tmp[i] > mx)
            mx = tmp[i];
    }

    dp[x][y] = mx + 1;
    return dp[x][y];
}

int main() {

    scanf("%d %d", &N, &M);

    table.clear();
    table.resize(N);
    for(int i = 0; i < N; i++) {
        string s;
        cin >> s;
        table[i] = s;
    }

    visit[0][0] = true;

    cout << dfs(0,0) << endl;
    visit[0][0] = false;

    return 0;
}

D. 결과