[백준 1261번] 알고스팟

풀이

---

BFS 해결가능하리라 보았지만 조금의 트릭이 있다.

벽을 만났을 경우 큐의 맨끝에 삽입하고 길을 만났을 경우에는 큐의 맨앞에 삽입해주어 길을 만나는 경우에 우선순위를 먼저 두어야한다.

오른쪽으로 한칸가서 벽이면 큐의 맨끝에 삽입

                            길이면 큐의 맨앞에 삽입

왼쪽으로 한칸가서 벽이면 큐의 맨끝에 삽입

                         길이면 큐의 맨앞에 삽입

위쪽으로 한칸가서 벽이면 큐의 맨끝에 삽입

                            길이면 큐의 맨앞에 삽입

아래쪽으로 한칸가서 벽이면 큐의 맨끝에 삽입

                            길이면 큐의 맨앞에 삽입

이순서대로 풀어야 우선순위에 맞게 길을찾는다. 벽을 최소한으로 부숴야하기때문에 길이 있다면 길로 먼저 갈수있도록 해주어야한다.

소스코드

---

#include <iostream>
using namespace std;
 
int n, m, map[103][103], wall_arr[103][103];
int que[100001], head=10,tail=10;
 
void push(int x, int y) {
    que[tail++] = x * 10000 + y;
}
 
int pop() {
    return que[head++];
}
 
void bfs() {
    while (head != tail) {
        int pos = pop();
        int x = pos / 10000;
        int y = pos % 10000;
 
        // 벽이 없으면 이전 정보 복붙
        // 벽이 있으면 wall_arr의 이전 정보 +1
        if (x + 1 <= n - 1 && map[x + 1][y] == 1 && wall_arr[x + 1][y] == -1) {
            wall_arr[x + 1][y] = wall_arr[x][y] + 1;
            push(x + 1, y); 
        }
        else if (x + 1 <= n - 1 && map[x + 1][y] == 0 && wall_arr[x + 1][y] == -1) {
            wall_arr[x + 1][y] = wall_arr[x][y];
            que[--head] = (x + 1) * 10000 + y;
        }
 
 
        if (x - 1 >= 0 && map[x - 1][y] == 1 && wall_arr[x - 1][y] == -1) {
            wall_arr[x - 1][y] = wall_arr[x][y] + 1;
            push(x - 1, y);
        }
        else if (x - 1 >= 0 && map[x - 1][y] == 0 && wall_arr[x - 1][y] == -1) {
            wall_arr[x - 1][y] = wall_arr[x][y];
            que[--head] = (x - 1) * 10000 + y;
        }
 
 
        if (y + 1 <= m - 1 && map[x][y + 1] == 1 && wall_arr[x][y + 1] == -1) {
            wall_arr[x][y + 1] = wall_arr[x][y] + 1;
            push(x, y + 1);
        }
        else if (y + 1 <= m - 1 && map[x][y + 1] == 0 && wall_arr[x][y + 1] == -1) {
            wall_arr[x][y + 1] = wall_arr[x][y];
            que[--head] = (x * 10000) + (y + 1);
        }
 
 
        if (y - 1 >= 0 && map[x][y - 1] == 1 && wall_arr[x][y - 1] == -1) {
            wall_arr[x][y - 1] = wall_arr[x][y] + 1;
            push(x, y - 1);
        }
        else if (y - 1 >= 0 && map[x][y - 1] == 0 && wall_arr[x][y - 1] == -1) {
            wall_arr[x][y - 1] = wall_arr[x][y];
            que[--head] = (x * 10000) + (y - 1);
        }
    }
}
 
int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char s;
            cin >> s;
            map[i][j] = s - '0';
            wall_arr[i][j] = -1;
        }
    }
    push(0, 0);
    wall_arr[0][0] = 0;
    bfs();
    cout << wall_arr[n - 1][m - 1] << '\n';
    return 0;
}