백준 2206 벽 부수고 이동하기 c++ (bfs)

문제 출처 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

bfs문제인데 벽을 한 번 뚫을 수 있다는 조건이 추가된 문제이다.

완전 탐색으로 모든 벽을 한 번씩 뚫고 bfs를 하는 방법은 시간 초과이기 때문에,

이 조건을 어떻게 풀어갈지 고민을 해야 한다.

 

bfs는 한 싸이클을 돌 때마다, 최대 4^i번 경로가 생성되고,(방향이 4개이기 때문에)

각 경로마다 벽이 있으면 탐색 종료, 벽이 없으면 계속 경로를 생성하면서
아직 방문하지 않은 칸을 탐색하며 도착지로 뻗어나간다.

단, 문제에서 벽을 한 개 부수고 이동하여도 된다고 하였기 때문에, 각 경로마다

한 번씩 벽을 만나도 부수고 이동할 수 있다.

 

따라서 현재 칸의 좌표를 저장하는 큐에 벽을 부수었는지를 추가로 저장해 주고,

queue<pair<pair<int,int>,int>> q  //first.first == row , first.second == column , second ==block

 

해당 칸에 도착하는 데에 벽을 부순 상태, 벽을 부수지 않은 상태별로 이동한 칸의 개수를 저장하는 배열을 만든다.

visited[1000][1000][2];

// [row][column][1] == 벽을 부수지 않은 상태에서의 해당 칸에 도착하는 데에 이동한 칸의 개수  

// [row][column][0] == 벽을 부순 상태에서의 해당 칸에 도착하는 데에 이동한 칸의 개수

 

그 후 시작점에서부터 다음과 같은 조건으로 bfs를 실행하면 된다.

 

1.다음 칸이 벽이고 부술 수 있을 때면 

 -벽을 부수었기 때문에 큐에 다음 칸의 좌표와 0을 넣어주고,

 -벽이 부서진 상태의 다음 칸에 도착하는 데에 이동한 칸의 개수를 넣어준다.

 

2.다음 칸이 벽이 아니고 아직 방문하지 않았다면

//해당 칸에 벽을 부수고 왔을 때, 부수지 않고 왔을 때 각각 비교하게 된다. 

 -큐에 다음 칸의 좌표와 현재 벽을 부수었는지 상태를 그대로 넣어주고,

 -다음 칸에 현재 칸의 도착하는 데에 이동한 칸의 개수를 넣어준다.  

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int r,c;
int visited[1000][1000][2];
int bfs(int row, int col, vector<string> &graph ) {
    queue<pair<pair<int, int>, int>> q;
    q.push({ {0,0},1 });
    visited[0][0][1] = 1;

    while (!q.empty()) {
        int current_r = q.front().first.first;
        int current_c = q.front().first.second;
        int block = q.front().second;
        q.pop();

        if (current_r == r - 1 && current_c == c - 1) { //도착지에 도달하면 return
            return visited[current_r][current_c][block];
        }

        for (int i = 0; i < 4; i++) {
            int next_r = current_r + dir[i][0];
            int next_c = current_c + dir[i][1];
            if (next_r >= 0 && next_r < r&& next_c >= 0 && next_c < c) {
                //다음 칸이 벽이고 뚫을 수 있을 때
                if (graph[next_r][next_c] == '1' && block) {
                    q.push({ {next_r,next_c} ,0 });
                    visited[next_r][next_c][block - 1] = visited[current_r][current_c][block] + 1;
                }
                //다음 칸이 0이고 방문하지 않았을 때
                else if (graph[next_r][next_c] == '0' && visited[next_r][next_c][block] == 0) {
                    q.push({ {next_r,next_c},block });
                    visited[next_r][next_c][block] = visited[current_r][current_c][block] + 1;
                }
            }
        }

    }
    return -1;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> r>>c;
    vector<string> graph(r);
    for (int i = 0; i < r; i++) {
        cin >> graph[i];
    }
    cout <<bfs(0, 0,graph);
    return 0;
}