C++ BOJ 2178 (나의 잘못된 풀이)

[Settpark]

• 처음엔 아래의 코드와 같이 문제를 해결했고,

    int distance = 0;
    while(!Q.empty()) {
        distance++;
        pair<int,int> cur = Q.front(); Q.pop();
        
        for (int dir = 0; dir<4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (board[nx][ny] != '1' || dis[nx][ny] != -1) continue;
            Q.push({nx, ny});
            dis[nx][ny] = distance;
        }
    }
    cout << dis[n-1][m-1];

4 6
101111
101010
101011
111011

1. 위와 같이 문제가 주어질 때 BFS를 10번 실행할 때까지는 문제가 없다. 왜냐면 단방향이니까 하지만, 문제는 아래처럼 될때이다.

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 -1 -1 
3 5 6 -1 -1 -1

2. 위의 결과 처럼 단방향이 아니라 11번째 시행할 때와 같이 오른쪽과 아래에 있으면,
3. 아래쪽 12에 대한 BFS를 진행하고 13을 기록하고

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 13 -1 
3 5 6 -1 -1 -1 

4. 오른쪽 12에 대한 BFS를 진행하고 14를 기록한다. (14를 기록해야하지만 14를 기록할 수 있는 공간이 없다.)

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 13 -1 
3 5 6 -1 -1 -1 

5. 따라서 다음 13에 대한 BFS를 실행할 때, 15가 기록되버리고 만다.

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 13 15 
3 5 6 -1 15 -1 

올바른 코드는 아래처럼 현재 위치에 기록된 값 +1 만큼을 dis[nx][ny]에 기록하는 것이다.

dis[nx][ny] = dis[cur.first][cur.second] + 1;