(C++) - 백준(BOJ) 2206번 : 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

bfs문제였습니다.

 

풀이방법

 1. 정의하기 : 필요한 정보는 (i,j)의 맵에 도착했을 때 벽의 상태 w(0이면 부수지 않음, 1이면 부서짐) 입니다. 따라서 2차원을 두 가지로 나눠서 생각해야하므로 3차원의 visited배열을 이용해 거리와, 벽의 상태, 방문여부를 확인할 수 있도록 저장합니다.

 

 2. bfs함수 시행 : 두 가지 방식으로 시행됩니다.

  2-1. 이동할 수 있는 곳이라면

      현재 자리의 벽 상태 w를 그대로 가지고 옵니다. 그리고 1칸 이동했으므로 현재 거리에 + 1 해줍니다. 따라서

      다음 갈 곳(현재의 벽상태) = 현재까지의 거리(벽의 상태 : 0 또는 1) + 1입니다.

  2-2. 벽을 여태 부순 적이 없고 다음 갈 자리는 벽이라면

      다름 갈자리의 벽을 부숩니다. 따라서 다음 자리의 w는 1이며 이전 자리의 벽 상태에 해당하는 거리 + 1을 해줍니다.

이로써 벽을 부순 경우와 부수지 않은 경우를 모두 따져가며 bfs를 실행할 수 있습니다.

 

3. 도착하지 못했다면 -1을 반환합니다. 도착했다면 bfs의 특성상 제일 먼저 도착했으므로 벽을 부쉈든 안 부쉈든 도착지점의 거리를 반환합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,m;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int visited[1001][1001][2];
int board[1001][1001];

int bfs(int i,int j){
    queue <tuple<int,int,int>> q;
    q.push({i,j,0});
    visited[i][j][0] = 1;

    while(!q.empty()){
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int w = get<2>(q.front());
        q.pop();
        if(x==n-1 && y == m-1) return visited[x][y][w];
        for(int i = 0 ; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
            if(visited[nx][ny][w]) continue;

            //갈 수 있는 곳이면 이전 state + 1이 현재까지의 경로
            if(!board[nx][ny]){
                visited[nx][ny][w] = visited[x][y][w] + 1;
                q.push({nx,ny,w});
            }
            
            //부순 적이 없고 현재는 벽이라면
            if(!w && board[nx][ny]){
                visited[nx][ny][1] = visited[x][y][0] + 1;
                q.push({nx,ny,1});
            }

            
        }
    }
    return -1;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%1d",&board[i][j]);
    cout << bfs(0,0);
}