[백준] 1103: 게임

0. 문제 주소

 

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

1103번: 게임

 

 

1. 풀이

 

약간 내리막길 문제랑 비슷한 느낌이 들었다.

 

맨 처음엔 칸 별로 연결관계를 만들어 BFS를 돌리려고 했으나... 멍청한 생각이었다.

 

 

DFS + DP의 풀이를 사용한다. top-down은 어렵다 ㅠ

 

 

주의해야 할 점은 cycle의 유무이다.

 

[PS/BFS & DFS] - [BOJ] 9466: 텀 프로젝트에서 DFS를 이용해 cycle 유무를 판단할 때, finished 배열을 사용했는데,

 

이 문제의 경우엔 그냥 순회 도중에 이미 방문했다고 표시되어있는 곳을 재방문할 때 cycle이 발생한다고 판단해도 된다.

 

재귀 호출 도중 cycle이 발생하면 -1 출력 후 바로 exit(0)으로 프로그램을 종료시키고,

 

나머지 경우엔 dp 테이블을 아래와 같은 dfs 함수로 채워나간다.

 

int dfs(int i, int j){
    if (visited[i][j]){
        cout << "-1\n";
        exit(0);
    }

    if (dp[i][j]) return dp[i][j];

    visited[i][j] = true;
    for (int d=0;d<4;d++){
        int ni = i + di[d] * grid[i][j], nj = j + dj[d] * grid[i][j];
        if (ni < 0 || ni >= N || nj < 0 || nj >= M || grid[ni][nj] == 0) continue;

        dp[i][j] = max(dp[i][j], dfs(ni, nj) + 1);
    }
    visited[i][j] = false;

    return dp[i][j];
}

 

 

 

1. 이미 계산한 부분은 다시 계산하지 않는다.

 

    if (dp[i][j]) return dp[i][j];

 

 

2. dp[i][j] 는 i행 j열의 칸에서 출발할 때의 최대 이동 횟수이다.

 

        dp[i][j] = max(dp[i][j], dfs(ni, nj) + 1);

 

 

3. 방문 했던 곳을 다시 방문하지 않는 것이 아니다(중요). 

 

    visited[i][j] = true;
    for (int d=0;d<4;d++){
        ~~~
    }
    visited[i][j] = false;

 

경우에 따라 다른 곳을 거쳐 재방문할 수 있고, 이 경우 최댓값이 갱신될 수 있다.

재방문하면 cycle 아니냐? 할 수 있는데, 뱀 게임을 생각하면 쉽다.

 

 

뱀의 몸을 "현재 내가 탐색하고 있는 경로"라고 생각하면 된다.

 

 

사이클이 발생했다는 건 뱀의 머리가 자신의 몸통에 닿은 상황이고,

 

3번에서 말한 재방문을 하는 상황은, 뱀이 한 번 지나갔던 칸을, 이번에는 다른 방법으로 돌아서 지나가는 상황이다.

 

 

최장 길이라고 해서 무조건 BFS라고 생각하는 습관을 버리기 좋았던 문제.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define MAX 53

using namespace std;

int N, M;
int grid[MAX][MAX];
bool visited[MAX][MAX];
int dp[MAX][MAX];
int di[4] = {0, 0, -1, 1};
int dj[4] = {1, -1, 0, 0};

int dfs(int i, int j){
    if (visited[i][j]){
        cout << "-1\n";
        exit(0);
    }

    if (dp[i][j]) return dp[i][j];

    visited[i][j] = true;
    for (int d=0;d<4;d++){
        int ni = i + di[d] * grid[i][j], nj = j + dj[d] * grid[i][j];
        if (ni < 0 || ni >= N || nj < 0 || nj >= M || grid[ni][nj] == 0) continue;

        dp[i][j] = max(dp[i][j], dfs(ni, nj) + 1);
    }
    visited[i][j] = false;

    return dp[i][j];
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    for (int i=0;i<N;i++){
        string row;
        cin >> row;
        for (int j=0;j<M;j++){
            char temp = row[j];
            if (temp == 'H') continue;
            else grid[i][j] = temp - '0';
        }
    }

    cout << dfs(0, 0) + 1;


    return 0;
}