[Algorithm]Baekjoon 1103 : 게임

https://www.acmicpc.net/problem/1103

1103번: 게임

 
int n, m;
int board[50][50] = { 0 };
int dp[50][50] = { 0 };
bool visited[50][50] = { false };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int answer = 0;
 
 
bool IsInRange(int y, int x)
{
    if (y < 0 || y >= n || x < 0 || x >= m) return false;
    return true;
}
 
int DFS(int y, int x)
{
    if (!IsInRange(y, x) || board[y][x] == -2) return 0;
    if (visited[y][x])
    {
        cout << -1;
        exit(0);
    }
 
    if (dp[y][x] != 0) return dp[y][x];
 
    dp[y][x] = 0;
    visited[y][x] = true;
 
    for (int i = 0; i < 4; ++i)
    {
        int nextY = y + dirs[i][0] * board[y][x];
        int nextX = x + dirs[i][1] * board[y][x];
 
        dp[y][x] = max(dp[y][x], DFS(nextY, nextX) + 1);
    }
 
    visited[y][x] = false;
 
    return dp[y][x];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < s.size(); ++j)
        {
            if (s[j] == 'H') board[i][j] = -2;
            else board[i][j] = s[j] - '0';
        }
    }
 
    int answer = DFS(0, 0);
 
    cout << answer;
}

깔끔한 아이디어가 떠오르지 않아 고민하다 다른사람 풀이를 참고했다.

예전같았으면 또 혼자 풀어보겠답시고 시간 더 썼을거같긴한데, 그런식으로 시간소모하기에는 더이상 시간이 없어서..

 

일단 dp[y][x]의 의미는, 해당 좌표에서 최대로 뻗어나갈 수 있는 값이다. 그리고 visited로 추가 체크를 한번 더 해야하는데, 왜냐하면 사이클이 존재하는지 체크해야하기 때문이다. 문제에서 무한히 판안에서 순회할 수 있으면 -1을 출력해줘야한다고 했기 때문에 필요하다.

하나의 깊이를 탐색하는 과정에서, 이미 이전에 탐색했던것을 재탐색하려할 경우 사이클이 있다고 판단하여 -1을 출력하고 종료시킨다. 이외에 범위를 벗어난다거나, 목표지점이 구멍이라면 더이상 살아남을 방법이 없기때문에 0을 리턴한다.

 

즉, 탐색은 기본적으로 동전이 살아남기 위한 코드로 작성하고, 더이상 움직이는게 불가능할 경우는 dp테이블을 업데이트, 사이클을 탐지하면 -1을 출력하고 종료시키면 된다.