[BFS] 2206번 벽 부수고 이동하기

2206번 벽 부수고 이동하기

 

https://www.acmicpc.net/problem/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을 출력한다.

 

예제 입력

6 4
0100
1110
1000
0000
0111
0000

4 4
0111
1111
1111
1110

 

예제 출력

15

-1

 

해결방법

 

🔥틀렸습니다🔥

처음에는 Single-Source (one-to-all) 방식의 다익스트라 알고리즘을 활용해 문제를 풀었다

 

2차원 배열에서 각 노드를 이동하여 목표 노드에 도달해야 하고, 또한 최소 비용이어야 한다

여기서 비용은 각 노드를 이동할 때, +1의 비용이 발생한다

벽을 부수는데는 비용이 발생하지 않는다 (하지만 벽은 단 1개만 부술 수 있음)

 

하지만 굳이 다익스트라 알고리즘이 아닌 BFS 탐색을 수행할 수 있었다

왜냐하면 노드 간의 비용은 '1'로 동일하다

가중치가 모두 다르다면 BFS 탐색 을 수행해야한다

 

 

⭐️솔루션⭐️

참고1

참고2

 

BFS 탐색을 통해 최단 경로를 구하는 코드를 작성해야 한다

 

벽을 하나만 부숴야하는 점이 까다로워서 구글링을 해봤다

그러다가 3차원 배열을 활용해서 문제를 해결하는 것을 참고했다

한 노드는 '벽을 부쉈을 경우', '벽을 부수지 않은 경우' 를 나타내기 위해

dist[MAX][MAX][2];

3차원 배열을 사용한다

처음 구현은 visit 2차원 배열을 만들어 이미 지나간 곳은 방문하지 않도록 했다

하지만 그렇게 구현한 코드는 예외케이스가 존재했다

 

따라서 아래의 조건을 설정해야 했다

⭐️ 한 노드는 '벽을 부수고 온 경우' '벽을 부수지 않고 온 경우' 최대 2번 방문 가능하다

 

벽을 만났을 경우와 벽이 아닌 경우를 나눠서 탐색을 수행했다

// 벽이 아니라면
if(map[nx][ny]==0 && dist[nx][ny][wall] == 0){
    dist[nx][ny][wall] = dist[x][y][wall] + 1;
    q.push(node(nx,ny,wall));
}
// 만약 벽을 만나면
else if(map[nx][ny]==1 && wall==0 && dist[nx][ny][wall]==0){
    dist[nx][ny][wall+1] = dist[x][y][wall] + 1;
    q.push(node(nx,ny,wall+1));
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;

struct node{
    int x,y,wall;
    node(int _x,int _y,int _wall) :x(_x),y(_y),wall(_wall){}
};

int n,m;

int map[MAX][MAX];
int dist[MAX][MAX][2];  // [0]: 벽을 부수지 않음, [1]: 벽을 부숨

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

void bfs(){
    queue<node> q;
    q.push(node(0,0,0));
    dist[0][0][0] = 1;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int wall = q.front().wall;
        q.pop();
        
        if(x==n-1 && y==m-1){
            printf("%d\n",dist[x][y][wall]);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            
            // 벽이 아니라면
            if(map[nx][ny]==0 && dist[nx][ny][wall] == 0){
                dist[nx][ny][wall] = dist[x][y][wall] + 1;
                q.push(node(nx,ny,wall));
            }
            // 만약 벽을 만나면
            else if(map[nx][ny]==1 && wall==0 && dist[nx][ny][wall+1]==0){
                dist[nx][ny][wall+1] = dist[x][y][wall] + 1;
                q.push(node(nx,ny,wall+1));
            }
        }
    }
    printf("%d\n",-1);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    scanf("%d %d",&n,&m);
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&map[i][j]);
            dist[i][j][0] = 0;
            dist[i][j][1] = 0;
        }
    }
    
    bfs();
}