[백준 2206번]벽 부수고 이동하기

풀이

---

벽을 하나씩 부수면서 BFS를 돌리면 시간초과가 나오게 되는 문제이다.

그래서 3번의 BFS를 돌려서 해결할 수 있는 방법으로 풀었다.

1. 시작지점 (0,0)부터 BFS를 돌린다. (한칸 갈때마다 몇칸을 이동했는지 정보를 넣어둔다.)

2. 끝지점 (N,M)부터 BFS를 돌린다. (한칸 갈때마다 몇칸을 이동했는지 정보를 넣어 둔다.)

3. 벽의 정보(1이 있는곳)가 들어 있는 큐에서 하나씩 꺼내서 상하좌우로 이동할 수 있는지 판별한다.

4. 상하좌우로 이동하였을 경우 시작지점의 정보 1개와 끝지점의 정보 1개가 있는지 판별한다.

5. 두개의 정보가 모두 있을 경우에만 경로 계산을 한다.

소스 코드

---

#include <iostream>
using namespace std;
 
int n, m,map[1001][1001], copy_map[1001][1001];
int que_x[10001], que_y[10001], head_x,tail_x,head_y,tail_y,Min = 999999;
int que_one[2][10001], head_one = 0, tail_one = 0;
int start_x, start_y, end_x, end_y;
 
void push(int x, int y) {
    que_x[tail_x++] = x;
    que_y[tail_y++] = y;
}
 
int pop_x() {
    return que_x[head_x++];
}
 
int pop_y() {
    return que_y[head_y++];
}
 
void bfs(int a) {
    while (1) {
        int x = pop_x();
        int y = pop_y();
 
        if (x + 1 <= n - 1 && copy_map[x + 1][y] == 0) {
            copy_map[x + 1][y] = copy_map[x][y] + 1;
            push(x + 1, y);
        }
        if (x - 1 >= 0 && copy_map[x - 1][y] == 0) {
            copy_map[x - 1][y] = copy_map[x][y] + 1;
            push(x - 1, y);
        }
        if (y + 1 <= m - 1 && copy_map[x][y+1] == 0) {
            copy_map[x][y+1] = copy_map[x][y] + 1;
            push(x, y+1);
        }
        if (y - 1 >= 0 && copy_map[x][y-1] == 0) {
            copy_map[x][y-1] = copy_map[x][y] + 1;
            push(x, y-1);
        }
 
        if (head_x == tail_x) {
            if (a == 0) {
                start_x = x;
                start_y = y;
            }
            else if (a == 1) {
                end_x = x;
                end_y = y;
            }
            break;
        }
    }
}
 
void copy_m() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            copy_map[i][j] = map[i][j];
        }
    }
}
 
void debugging() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << copy_map[i][j] << " ";
        }
        cout << '\n';
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char aa;
            cin >> aa;
            map[i][j] = aa - '0';
            if (map[i][j] == 1) {
                que_one[0][tail_one] = i;
                que_one[1][tail_one] = j;
                tail_one++;
            }
        }
    }
    
    copy_m();
    head_x = tail_x = head_y = tail_y = 0;
    copy_map[0][0] = 2;
    push(0, 0);
    bfs(0);
    head_x = tail_x = head_y = tail_y = 0;
    copy_map[n-1][m-1] = 10002;
    push(n-1, m-1);
    bfs(1);
 
    while (head_one != tail_one) {
        int x = que_one[0][head_one];
        int y = que_one[1][head_one];
        head_one++;
 
        int start_min = 10000;
        int end_min = 98765432;
 
        if (x + 1 <= n - 1) {
            if (copy_map[x + 1][y] !=1 && copy_map[x+1][y]!=0) {
                // 시작점에서 출발한건지, 끝점에서 출발한건지 판별
                if (copy_map[x + 1][y] < 10000) {  // 시작지점부터 출발
                    if (start_min > copy_map[x + 1][y]) {
                        start_min = copy_map[x + 1][y];
                    }
                }
                else if (copy_map[x + 1][y] > 10000) { // 끝점부터 출발
                    if (end_min > copy_map[x + 1][y]) {
                        end_min = copy_map[x + 1][y];
                    }
                }
            }
        }
        if (x - 1 >= 0) {
            if (copy_map[x - 1][y] != 1 && copy_map[x - 1][y] != 0) {
                // 시작점에서 출발한건지, 끝점에서 출발한건지 판별
                if (copy_map[x - 1][y] < 10000) {  // 시작지점부터 출발
                    if (start_min > copy_map[x - 1][y]) {
                        start_min = copy_map[x - 1][y];
                    }
                }
                else if (copy_map[x - 1][y] > 10000) { // 끝점부터 출발
                    if (end_min > copy_map[x - 1][y]) {
                        end_min = copy_map[x - 1][y];
                    }
                }
            }
        }
        if (y + 1 <= m - 1) {
            if (copy_map[x][y+1] != 1 && copy_map[x][y+1] != 0) {
                // 시작점에서 출발한건지, 끝점에서 출발한건지 판별
                if (copy_map[x][y+1] < 10000) {  // 시작지점부터 출발
                    if (start_min > copy_map[x][y+1]) {
                        start_min = copy_map[x][y+1];
                    }
                }
                else if (copy_map[x][y+1] > 10000) { // 끝점부터 출발
                    if (end_min > copy_map[x][y+1]) {
                        end_min = copy_map[x][y+1];
                    }
                }
            }
        }
        if (y - 1 >= 0) {
            if (copy_map[x][y - 1] != 1 && copy_map[x][y - 1] != 0) {
                // 시작점에서 출발한건지, 끝점에서 출발한건지 판별
                if (copy_map[x][y - 1] < 10000) {  // 시작지점부터 출발
                    if (start_min > copy_map[x][y - 1]) {
                        start_min = copy_map[x][y - 1];
                    }
                }
                else if (copy_map[x][y - 1] > 10000) { // 끝점부터 출발
                    if (end_min > copy_map[x][y - 1]) {
                        end_min = copy_map[x][y - 1];
                    }
                }
            }
        }
 
        if (start_min != 10000 && end_min != 98765432) {
            if (Min > start_min + (end_min - 10000)) {
                Min = start_min + (end_min - 10000);
            }
        }
    }
 
    if (Min == 999999) {
        cout << -1 << '\n';
        return 0;
    }
    cout << Min-1 << '\n';
 
    return 0;
}

--> Debugging 함수는 결과값이 제대로 동작하고 있는지 확인할 때 쓰는 함수.