2206 벽 부수고 이동하기

BOJ::2206 벽 부수고 이동하기

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

이 문제 푸는데 정말 오래 걸렸다.

https://www.acmicpc.net/problem/2178 와 같은 미로찾기의 상위 문제

처음에는 뚫을 수 있는 벽에 대해서만 벽을 뚫어 bfs한 결과 중 최소값을 출력하려고 했는데 계속 시간 초과가 났다. 그래서 다른 방법으로 3차원배열 d를 만들어 d[][][0]은 벽을 뚫지 않은 상태, d[][][1]은 벽을 뚫은 상태 로 생각하고 풀었다.

이문제를 풀 수 있으면

https://www.acmicpc.net/problem/14442 벽부수고 이동하기 2 도 비교적 쉽게 풀 수 있다.

<C++>

#include <stdio.h>
#define MIN(a, b) ((a)<(b))?(a):(b) 
#define SZ 1000
#define QSZ 1000001 // 큐사이즈
 
//좌표 저장용
struct P {
    int x, y;
    bool used;//벽 뚫기 사용했는지 안했는지 확인용
    P() {}
    P(int x, int y, bool used) :x(x), y(y), used(used) {}
};
 
int n, m;
int map[SZ][SZ];
int d[SZ][SZ][2];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
P q[QSZ];
int rear, front;
 
void push(P p) {
    rear = (rear + 1) % QSZ;
    q[rear] = p;
}
P pop() {
    front = (front + 1) % QSZ;
    return q[front];
}
bool isEmpty() {
    return rear == front;
}
 
void bfs() {
    //d배열 초기화
    d[0][0][0] = 1;
    d[0][0][1] = 1;
    push(P(0, 0, false));
 
    while (!isEmpty()) {
        P p = pop();
        int x = p.x;
        int y = p.y;
        bool used = p.used;
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
                //길일때
                if (map[ax][ay] == 0) {
                    //벽뚫기 사용하지 않은 경우
                    if (!used) {
                        if (d[ax][ay][0] == 0 || d[ax][ay][0] > d[x][y][0] + 1) {
                            d[ax][ay][0] = d[x][y][0] + 1;
                            push(P(ax, ay, false));
                        }
                    }
                    //벽뚫기 사용한 경우
                    if (d[ax][ay][1] == 0 || d[ax][ay][1] > d[x][y][1] + 1) {
                        d[ax][ay][1] = d[x][y][1] + 1;
                        push(P(ax, ay, true));
                    }
                }
                else {
                    //벽을 뚫는 경우
                    if (!used) {
                        if (d[ax][ay][1] == 0 || d[ax][ay][1] > d[x][y][0] + 1) {
                            d[ax][ay][1] = d[x][y][0] + 1;
                            push(P(ax, ay, true));
                        }
                    }
                }
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c", &map[i][j]);
            map[i][j] -= '0';
        }
    }
 
    bfs();
 
    int res1 = d[n - 1][m - 1][0]; //벽을 안뚫었을때 최소값
    int res2 = d[n - 1][m - 1][1]; //벽을 뚫었을때 최소값
    int res = 0;
 
    if (res1 != 0 && res2 != 0) {
        res = MIN(res1, res2);
    }
    else if (res1 == 0) {
        res = res2;
    }
    else if (res2 == 0) {
        res = res1;
    }
 
    if (res == 0) res = -1;
    printf("%d\n", res);
}