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

BFS를 이용하여 해결하는 문제인 것은 알고 있었지만 그냥 최단 거리가 아닌 벽을 하나 부순다는 상황이 주어져서 더욱더 혼란스러워졌다.

 

2일 동안 생각을 해보고 도전을 해봤지만 실패... 

 

혼자서는 도저히 못 풀겠다는 생각이 들어 인터넷 블로그의 힘을 살짝 빌렸다..ㅠ

다른 사람들이 해결했던 방법들을 보고 이해한 후 문제를 보고 다시 풀었다.....

 

해결 방법

최단 거리를 측정하는 패턴은 기존 벽을 부수지 않고 이동하는 것과 동일하다. 

하지만 최단거리로 가기 위해 벽을 한번 부수려면 모든 벽을 탐지한 후 벽을 부숴야 한다.

출발하자마자 벽을 부수고 가는 것이 최단 거리일 수 있지만 도착지가 벽으로 둘러 싸여 있는 경우 벽 부수는 스킬을 아껴 놓아야 한다.

해당 사례가 아래 그림이다.

출발지	0(a)	0(b)	0(c)
1(x)	1	1	0(d)
0(h)(x)	0(g)	0(f)	0(e)
0(i)(x)	1	1	1
0(j)(x)	1	1	1
0(k)(x)	0(l)(x)	1(부숨)	도착지

a - b - c - d - e -... - k 순서로 돌아서 간다음에 도착지 앞의 벽을 부수는 것이 최단 거리이다.

하지만 처음부터 부수게 되면 x로 표현된 길을 따라가다 보면 도착지 앞의 벽을 부수지 못하게 된다.

 

이것을 구별하기 위해 3차원 배열을 이용하여 스킬을 이미 사용한 경우와 스킬을 사용할 수 있는 경우 2가지로 나누어서 사용하였다.

 

#include <bits/stdc++.h>

int bwN,bwM;
bool brList[1001][1001] = {0};
int brVisited[2][1001][1001] = {0};       // 0: 스킬 쓴 상태, 1: 스킬 안쓴 상태

queue<pair<pair<int, int>,bool>> brQ;

int brBFS(){
    brQ.push({{0,0},true});
    brVisited[1][0][0] = 1;
    
    int dx[] = {1,-1,0,0};
    int dy[] = {0,0,1,-1};
    
    while(!brQ.empty()){
        int x = brQ.front().first.first;
        int y = brQ.front().first.second;
        bool check = brQ.front().second;
        brQ.pop();
        
        if(x == bwN - 1 && y == bwM - 1){
            return brVisited[check][x][y];
        }
        
        for(int i=0;i<4;i++){
            int mx = x + dx[i];
            int my = y + dy[i];
            
            if(mx<0 || mx>bwN -1 || my<0 || my > bwM - 1)
                continue;
            
            if(brList[mx][my] == 1 && check){
                brVisited[0][mx][my] = brVisited[1][x][y] + 1;
                brQ.push({{mx,my},false});
            }
            else if(brVisited[check][mx][my] == 0 && brList[mx][my] == 0){
                brVisited[check][mx][my] = brVisited[check][x][y] + 1;
                brQ.push({{mx,my},check});
            }
            
        }
        
    }
    return -1;
}

void brokeWall(){
    cin>>bwN>>bwM;
    
    for(int i=0;i<bwN;i++){
        for(int j=0;j<bwM;j++){
            int input;
            scanf("%1d",&input);
            brList[i][j] = input;
        }
    }

    cout<<brBFS()<<endl;
   
}

 

 

 

 

□ 사용한 반례

5 8
01000000
01010000
01010000
01010011
00010010

ans: 20


8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

ans: 29


3 6
010000
010111
000110

ans: 12

1 1
0

ans: 1