[C/C++] 백준 #2206 벽 부수고 이동하기(너비 우선 탐색)

#2206은 평범한 너비 우선 탐색 문제는 아닙니다.  벽을 한번까지는 부실 수 있는 조건이 있기 때문에, 이에 대해서 처리를 해주어야 합니다.

 

문제의 링크는 다음과 같습니다.

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

2206번: 벽 부수고 이동하기

 

이 문제는 한번 이동하는데 항상 1이라는 가중치가 있는 그래프이기 때문에, 벽을 뚫고 갈 수 있다는 것을 원칙을 정해서 풀면 됩니다.

 

break a wall

 

1) 벽을 한번 부수고 지나간 길은 음의 값으로 경로값을 적는다.

2) 음의 경로값은 벽을 한번도 부수지 않은 경로값으로 덮어쓸 수 있다.

3) 음의 경로값을 가진 경우 벽은 장애물이다.

4) 양의 경로값을 가진 경우 벽을 부수고 진행할 수 있다.

 

만약 한번 이동할 때마다 가중치가 달라진다면 위의 법칙만으로는 최적의 경로를 찾을 수가 없습니다.  비슷한 부분도 있지만, 그렇지 않은 부분도 존재하기 때문이죠.

 

너비 우선 탐색으로 했기 때문에 위의 원칙하에 프로그램할 수 있는 것이고, 깊이 우선탐색을 사용한다면, 경우의 수가 상당히 많아질 수밖에 없습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2206 - Move with Breaking Walls
//        - by Aubrey Choi
//        - created at 2019-06-15
//------------------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    int n, m, s, i, j;
    static int node[1000][1000];
    static char map[1000][1000];
    const int dxy[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
    std::queue<int> queue;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++)
    {
        char str[1001];
        scanf("%s", str);
        for(j = 0; j < m; j++) map[i][j] = str[j]-'0';
    }
    node[0][0] = 1;
    queue.push(0);
    while(!queue.empty())
    {
        s = queue.front(); queue.pop();
        if(s == (n - 1) * 1000 + m - 1) break;
        int y = s / 1000, x = s % 1000;
        int d = node[y][x];
        for(i = 0; i < 4; i++)
        {
            int nx = x + dxy[i][0], ny = y + dxy[i][1];
            if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if(d < 0)
            {
                if(map[ny][nx] == 1) continue;
                if(node[ny][nx] != 0) continue;
                node[ny][nx] = d - 1;
            }
            else
            {
                if(map[ny][nx] == 1)
                {
                    if(node[ny][nx] != 0) continue;
                    node[ny][nx] = -d - 1;
                }
                else
                {
                    if(node[ny][nx] > 0) continue;
                    node[ny][nx] = d+1;
                }
            }
            queue.push(ny * 1000 + nx);
        }
    }
    if(node[n - 1][m - 1] == 0) puts("-1");
    else if(node[n - 1][m - 1] < 0) printf("%d\n", -node[n - 1][m - 1]);
    else printf("%d\n", node[n - 1][m - 1]);
    return 0;
}