백준) 2206 벽 부수고 이동하기

벽 부수고 이동하기

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

지도가 제공되고 최단 경로의 길이를 구하는 문제다.

벽을 한 개는 부술 수 있다는 추가 조건이 있긴 하지만, 최단 경로 문제니까 BFS로 풀어보자.

BFS는 완전탐색 알고리즘이므로, 잘만 하면 벽을 전부 하나씩 부수고 탐색하는 케이스들도 전부 탐색할 수 있다.

평행세계를 생각해보면 좋은데, 여기서 벽을 부술지 돌아갈지를 두 차원으로 나눠서 생각하는 것이다.

그러면 부순 세계와 돌아간 세계는 독립되고 서로 영향을 주지 않는다.

이를 구현하기 위해, BFS에서 주로 쓰는 VISIT배열을 삼차원으로 만든다.

즉, 이차원 배열이 두 개 쌓인 것이다. 기본적으론 벽을 부수지 않은 세계에서 출발하며,

벽을 만날 시에 벽을 부수고 다른 세계로 넘어가는 경우와, 벽을 돌아서 가는 경우를 모두 큐에 넣으면 된다.

이 후의 탐색은 개별적으로 진행된다.

코드로 옮기면 다음과 같다.

STL을 쓰지 않아 코드가 매우 길다.

#include <stdio.h>
 
typedef struct col {
    int x, y, z;
};
col que[2000000];
int que_front, que_back;
#define que_size 2000000
void que_push(int x, int y, int z) {
    que[que_back] = { x,y,z };
    que_back = (que_back + 1) % que_size;
}
col que_pop() {
    col tmp = que[que_front];
    que_front = (que_front + 1) % que_size;
 
    return tmp;
}
int abs(int x) {
    return x > 0 ? x : -x;
}
 
int n, m;
char buf[1001];
int map[1000][1000];
int visit[1000][1000][2];
int dir[4][2] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
 
void bfs(int x, int y, int z) {
    que_push(x, y, z);
    visit[x][y][0] = 1;
 
    int cnt = 2;
    while (que_front != que_back) {
 
        int size = abs(que_front - que_back);
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4; ++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
                int zz = tmp.z;
 
                if (xx < 0 || yy < 0 || xx >= n || yy >= m)
                    continue;
 
                if (visit[xx][yy][zz])
                    continue;
 
                if (map[xx][yy] == 0) {
                    que_push(xx, yy, zz);
                    visit[xx][yy][zz] = cnt;
                }
 
                if (map[xx][yy] == 1) {
                    if (zz == 1)
                        continue;
                    else {
                        que_push(xx, yy, 1);
                        visit[xx][yy][1] = cnt;
                    }
                }
            }
        }
        cnt++;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < m; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    bfs(0, 0, 0);
 
    int ans1 = visit[n - 1][m - 1][0];
    int ans2 = visit[n - 1][m - 1][1];
 
    if (ans1 == 0 && ans2 == 0)
        printf("-1");
    else if (ans1 == 0)
        printf("%d", ans2);
    else if (ans2 == 0)
        printf("%d", ans1);
    else
        printf("%d", ans1 < ans2 ? ans1 : ans2);
 
    return 0;
}