2206

백준 2206번

Link: 2206번: 벽 부수고 이동하기

---

문제 설명

예전에 한번 풀어봤던 벽부수고 이동하는 문제.

간만에 다시한번 풀어봤는데, 그때 답보고 풀어서 그런지 다시봐도 새롭더라.

여러번 거치다 보니 BFS로 거리 구하는 틀이 거의 정형화됐는데, 예전에는 visit 배열을 만드는 대신 거리를 계산하는 배열을 만들어서 거리를 쟀었다.

이 문제도 그렇게 풀었는데, 거리 계산 배열을 3차원으로 만들어 벽을 안부쉈을 경우와 부쉈을 경우로 나눠 거리를 구한다.

큐에도 출발점과 벽 부술수 있는 횟수를 넣고 출발하는데, 만약 목적지에 도착했다면 거리 배열[x][y][남은 부술수있는 횟수] 값을 리턴해준다.

이외에는 BFS와 크게 다르지 않은데, 벽을 안부수고 0을 찾아 이동한 거리를 구해주고, 부술 수 있는 횟수가 남았으면 벽을 부수고 이동한 거리를 구한 다음 부술 수 있는 횟수를 1 빼준다.

이런식으로 목적지까지 찾아가서 남은 부술수 있는 횟수에 대한 거리를 구하면 끝.

이번에서야 예전 답을 좀 이해할 수 있을 것 같다.

다음에도 한번 더 풀어봐야지.

---

정답 코드

//
// Created by Keith_Lee on 03/04/2019.
//

#include <iostream>
#include <queue>

using namespace std;

struct Point{
    int x, y;
    int breakCount;
};

int map[1000][1000] = {0, };
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dist[1000][1000][2] = {0, };

int N, M;

int BFS(){
    queue<Point> Queue;
    Queue.push({0, 0, 1});
    dist[0][0][1] = 1;

    while(!Queue.empty()){
        int currentX = Queue.front().x;
        int currentY = Queue.front().y;
        int breakCount = Queue.front().breakCount;
        Queue.pop();

        if(currentX == N-1 && currentY == M-1){
            return dist[N-1][M-1][breakCount];
        }

        for(int i=0; i<4; i++){
            int nextX = currentX + dx[i];
            int nextY = currentY + dy[i];

            if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < M){
                if(map[nextX][nextY] == 0 && dist[nextX][nextY][breakCount] == 0){
                    dist[nextX][nextY][breakCount] = dist[currentX][currentY][breakCount] + 1;
                    Queue.push({nextX, nextY, breakCount});
                }
                else if(map[nextX][nextY] == 1 && breakCount > 0){
                    dist[nextX][nextY][breakCount-1] = dist[currentX][currentY][breakCount] + 1;
                    Queue.push({nextX, nextY, breakCount-1});
                }
            }
        }
    }

    return -1;
}

int main(){
    cin >> N >> M;

    for(int i=0; i<N; i++){
        string row;
        cin >> row;

        for(int j=0; j<M; j++){
            map[i][j] = row[j] - '0';
        }
    }

    cout << BFS() << '\n';

    return 0;
}

---