[백준][c++] 2206번: 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

문제 해석

• N*M 배열의 1,1 에서 N,M까지의 최단경로를 찾아내는 문제
• 0은 벽이 없고 1은 벽이 있는 칸
• 벽은 최대 한번까지 부술수 있다. 

 

풀이

 

큐를 이용한 BFS(너비 우선 탐색)으로 최단경로를 찾았습니다.

 

코드

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <climits>

using namespace std;


//입력부
static int n,m;
static int least = INT_MAX; //이동 횟수
vector<vector<int>> arr;
vector<vector<int>> visited;
static int dx[4] = {-1,1,0,0};
static int dy[4] = {0,0,-1,1};

//블록 구조체
struct point{
    int x,y,time,blockCrashed;
    point(int x, int y, int time, int blockCrashed) : x(x), y(y), time(time), blockCrashed(blockCrashed) {}
};

//해결부
void bfs(int x, int y){
    queue<point> q;
    q.push(point(x, y, 1, 0));
    visited[y][x] = 0;

    while (!q.empty()){
        point current = q.front();
        q.pop();

        //종점일 경우
        if(current.y ==n-1 &&current.x == m-1){
            least = current.time;
            break;
        }

        //좌우양옆 탐색
        for(int i=0; i<4; i++){
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];

            //(배열의 범위를 넘어감 || 경로가 더 길 경우) -> continue
            if(!(0 <= nx && nx < m && 0 <=ny && ny < n) || visited[ny][nx] <= current.blockCrashed){
                continue;
            }

            //이동 가능한 곳
            if(arr[ny][nx] == 0){
                visited[ny][nx] = current.blockCrashed;
                q.push(point(nx, ny, current.time+1, current.blockCrashed));
            }
            //벽이 있는 곳
            else{
                if(current.blockCrashed == 0){
                    visited[ny][nx] = current.blockCrashed + 1;
                    q.push(point(nx, ny, current.time+1, current.blockCrashed+1));
                }
            }
        }
    }
}

int main() {

    cin >> n >> m;

    arr = vector<vector<int>>(n, vector<int>(m));
    visited = vector<vector<int>>(n, vector<int>(m, INT_MAX));

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

    bfs(0,0);
    cout << (least == INT_MAX ? -1 : least) << endl;

    return 0;
}