[boj] 백준 2206 벽 부수고 이동하기 (c++) - BFS

[문제]

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

2206번: 벽 부수고 이동하기

 

[풀이]

보통의 BFS 문제에서 벽을 부수고 갈 수 있다는 조건이 하나 더 추가되었다.

따라서 기존 visited[][] 배열 역시 경로에서 벽을 부수고 왔는지, 아닌지를 구분할 수 있도록 3차원 배열로 선언하였으며 좌표와 그동안 벽을 부수고 왔는지 여부, 이동한 거리를 담는 구조체를 선언해서 queue에 넣어주도록 한다. 

 

코드상 구분해줘야 하는 경우는 다음 2가지이다.

1) 벽이 있고, 그동안 벽을 부수지 않고 온 경우 -> 벽을 부수고 이동한다.

2) 길이 있고, 아직 방문하지 않은 경우 -> 그 길로 이동한다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n, m;
int map[1001][1001];
bool visited[1001][1001][2] = {false, }; //벽을 부수고 왔는지, 아닌지 체크
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};

struct position{
    int r, c;
    int destroyed;
    int distance;
};

int bfs(){
    position p;
    p.r = p.c = 0;
    p.distance = 1;
    p.destroyed = 0;

    queue<position> q;
    q.push(p);

    visited[0][0][0] = true;

    while(!q.empty()) {
        position p = q.front();
        q.pop();

        if (p.r == n - 1 && p.c == m - 1) {
            return p.distance;
        }

        for (int i = 0; i < 4; i++) {
            int nr = p.r + dr[i];
            int nc = p.c + dc[i];

            if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;

            //벽이 있고, 안 부순 상태 -> 벽을 부수고 갈 수 있음
            if (map[nr][nc] && !p.destroyed) {
                visited[nr][nc][1] = true;
                q.push(position{nr, nc, 1, p.distance + 1});
            }

            //길이 있고, 방문 하지 않은 경우
            if (!map[nr][nc] && !visited[nr][nc][p.destroyed]) {
                visited[nr][nc][p.destroyed] = true;
                q.push(position{nr, nc, p.destroyed, p.distance + 1});
            }
        }
    }
    
    return -1;

}

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

    cin >> n >> m;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<m; j++){
            map[i][j] = s[j] - '0';
        }
    }

    cout << bfs();

}