[백준] 2206. 벽 부수고 이동하기

[문제]

 

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

[풀이]

 

 

NXM으로 표현되는 맵이 문제 입력으로 주어진다.

맵에는 벽이 존재하는데 최대 한번 벽을 부수고 이동할 수 있다.

이 때 시작점에서 (N,M)까지의 최단 거리를 구하면 된다.

 

최단거리를 구하는 문제라서 BFS를 사용하고 pos 구조체에 crash 변수를 추가하여 이전 경로에서 벽을 부수고 왔는지를 확인했다.

원래 visited 배열은 2차원 배열로 아래와 같이 선언했었다.

int visited[MAX][MAX]

 

하지만 해당 위치를 이미 방문했더라도 벽을 부수고 왔는지 아닌지에 따라 결과가 달라지므로

벽을 부수고 왔는지 아닌지에 대해서도 확인할 수 있도록 아래와 같이 수정했다.

int visited[MAX][MAX][2]

 

 

[코드]

 

#include <iostream>
#include <queue>

#define MAX 1001

using namespace std;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int N,M;
int map[MAX][MAX]={0,};
int visited[MAX][MAX][2]={0,};

struct pos{
    int x,y;
    bool crash;
};

int BFS()
{
    queue <pos> q;
    q.push({1,1,false});
    visited[1][1][0] =1;
    
    while(!q.empty()){
        
        int x = q.front().x;
        int y = q.front().y;
        bool check = q.front().crash;

        if(x == N && y == M)    return visited[x][y][check];
        
        q.pop();
        
        for(int i=0;i<4;i++){
            
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<1 || ny <1 || nx >  N || ny > M )  continue;
            if(map[nx][ny] == 1 && check)  continue;
            
            bool flag = false;
            if(map[nx][ny]==1)  flag = true;
            else    flag = check;
            
            if(visited[nx][ny][flag]!=0)    continue;
            
            q.push({nx,ny,flag});
            visited[nx][ny][flag]=visited[x][y][check]+1;
            
        }
    }
    return -1;
}

int main(void)
{
    scanf("%d %d",&N,&M);
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    cout << BFS();
}