[백준 알고리즘][BFS] 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을 출력한다.

문제 출처: 백준 온라인 저지 https://www.acmicpc.net/problem/2206

풀이

벽을 한번만 부술 수 있다는 게 어떤 뜻인지를 생각해봐야한다 지나갈 수 없는 1을 만났을 때 무조건 부수고 시작해야 좋은지 아닌지가 헷갈린다 

무조건 만나자마자 부수면 안된다 왜냐면  

6 4

0000

1110

1000

0000

0111

0000 이라면 2행 1열에서 만나는 1을 부수는 것 보다 5행 4열을 부수는 것이 더 최단경로이기 때문이다. 언제 벽을 부수는지에 대한 명확한 정의를 내리지 못하겠으므로 입력을 받을 때 1인 아이들을 다 큐에 넣어서 그 아이들을 하나씩 부수었을 때 경로를 보고 그 중에 가장 작은 아이가 정답이다. 그렇게 풀면 왠지 시간초과가 날 것 같지만 시간 제한이 2초니까 일단 코드로 짜본다.

언제 벽을 부수는 게 좋은지 판단할 수 없어서 모든 경우를 다 풀어보니 바로 시간 초과가 나왔다.

질문검색이랑 다른 풀이들을 보니까 한번 BFS를 통해서 풀 수 있다고 한다 풀이를 통해 이해가 약간 되었는데 큐에 현재 위치한 곳이 벽을 부수고왔는지 아닌지를 표시해서 큐가 빌 때까지 가장 최단거리안에 도착할 수있도록 하면된다 벽을 부수고 지나가는 경로라면 큐에 TRUE를 함께 넣어서 TRUE인 값을 큐에서 뺄 때는 벽을 더이상 부술 수 없게 한다!

시간초과가 뜨는 문제는 위와 같은 풀이로 해결했다 그런데 예외케이스가 있었다.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100

00010100 

이와 같은 케이스에 8, 2 좌표를보면 7, 2에서 벽을 한번 뚫고 오는 경우와 8, 1에서 쭉 오는 경우가 있는데 먼저오는 아이가 지나가면서 좌표를 체크해버려서 두번째애가 오지를 못한다 한번 방문한 경우 다시 방문안하지 않는다고 생각해버려 체크해주는 방식을 바꿔야했다. 원래는 한 곳에는 한번만 지나간다 생각해서 한번 지나가면 그 자리를 벽으로 만들었는데, 그렇게 하지 않아야했다. 

고쳐야하는 부분이 2가지였다

1. 한 곳에는 벽을 부수고왔을 경우와 벽을 안부수고 온 2가지의 경우가 있다 즉, 한 곳에 최대 2번까지 방문을 할 수있다.

2. 기존에 지나갔을 때 벽으로 만들어버린 방식이 아닌 다른 방식으로 지나감을 표시해줘야한다 지나감을 표시하지 않으면 무한루프에 걸려서 계속해서 지나갔던 곳으로도 방문한다

그래서 새로운 배열을 하나 만들어서 하나의 좌표에 대해서 벽을 부수고 지나갔는지, 안부수고 지나갔는지를 표시해줬다.

+ 추가 2018.11.02

이 문제를 왜 다시 풀어보지 않았을까 후회한다. 배열을 3차원 써서 풀었던 기억 자체는 금방 떠올랐었는데 복습을 안해두니 다시 풀려고 했을 때 막히는 부분이 있었다. 

위에서도 고쳐야하는 부분이라고 언급한 것 처럼 visit 배열에서 해당하는 곳을 부수고 간 경우와 부수지 않고 간 경우 2가지가 있기때문에 3차원 배열을 통해서 해결해야한다. 지난번 이 문제를 풀 때는 3차원 로직에 대해 완벽한 이해가 안됐었나보다. visit배열은 이미 방문한 곳을 안가서 시간초과가 나지 않게 해주는 역할이었는데 시간초과가 났어서 포기했었던 것 같다. 방금 다시 풀었는데 간단한 문제였다. visit 자체를 큐에 넣고나서 pop할 때 1로 바꿔주다보니 이미 큐에 들어가있지만 pop이 안 된 경우에는 또 큐에 들어가는 문제가 있었다. 이런 간단한 부분을 놓치고 있었다니... 역시 공부는 꾸준히 꼼꼼히 해야함을 느낀다.

코드

#include<iostream>

#include<stdio.h>

#include<queue>

#define min(x, y) x > y ? y : x 

using namespace std;

 

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

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

class Graph{

public:

int N, M;

int map[101][101]; //원래 버전

int check[101][101][2];

struct ptr

{

int x;

int y;

int wall; //벽을 부수고 큐에 넣었는지 아닌지를 표시

};

queue<struct ptr> move;

Graph(){}

Graph(int i, int j)

{

N = i;

M = j;

}

 

int BFS()

{

int level=0;

struct ptr tmp, temp;

int i, j;

int qsize;

 

tmp.x = 1;

tmp.y = 1;

tmp.wall = 0; //아직 안부순경우

map[1][1] = 1;

move.push(tmp);

 

while(move.empty() != true)

{

qsize = move.size();

for(j=0; j<qsize ; j++){

tmp = move.front();

move.pop();

check[tmp.x][tmp.y][tmp.wall] = 1; //첫 시작에서 벽을 안부순 경우 지나감 -> 이 경우 시간초과 발생

if(tmp.x == N && tmp.y == M)

return level+1;

for(i=0; i<4; i++)

{

if(tmp.x + dx[i] <= 0  || tmp.y + dy[i] <= 0 ||

tmp.x + dx[i] > N  || tmp.y + dy[i] > M)

continue;

 

if(map[tmp.x+dx[i]][tmp.y+dy[i]] != 1 && tmp.wall == 0 && check[tmp.x+dx[i]][tmp.y+dy[i]][0] == 0 )

{ //원래 벽이 아닌 경우

temp.x =tmp.x + dx[i];

temp.y =tmp.y + dy[i];

temp.wall = 0;

move.push(temp);

}

else if(map[tmp.x+dx[i]][tmp.y+dy[i]] != 1 && tmp.wall == 1 

&& check[tmp.x+dx[i]][tmp.y+dy[i]][1] == 0)

{

temp.x =tmp.x + dx[i];

temp.y =tmp.y + dy[i];

temp.wall = 1;

     check[tmp.x][tmp.y][tmp.wall] = 1; //push 하기 전에 바꿔줘야함 위에 check는 삭제해야함

move.push(temp);

}

else if(map[tmp.x+dx[i]][tmp.y+dy[i]] == 1 && tmp.wall == 0 

&& check[tmp.x+dx[i]][tmp.y+dy[i]][1] == 0) 

{ //막혀있는 데 벽을 한번 뚫을 수 있을 경우

temp.x =tmp.x + dx[i];

temp.y =tmp.y + dy[i];

temp.wall = 1; //벽을 부숨

                                                check[tmp.x][tmp.y][tmp.wall] = 1; //push 하기 전에 바꿔줘야함

move.push(temp);

}

}

}

level++;

}

return N*M;

}

 

};

int main()

{

int i, j;

int n, m, result;

char input;

scanf("%d %d", &n, &m); 

scanf("%c", &input);

Graph G(n, m);

for(i=1; i<=n;i++){

for(j=1; j<=m; j++){

scanf("%c", &input);

G.map[i][j] = input - '0';

G.check[i][j][0] = 0; //벽을 부수지않은상태

G.check[i][j][1] = 0; 

}

scanf("%c", &input);

}

result = G.BFS(); 

if(result == n*m)

        printf("-1");

    else

        printf("%d\n", result);

return 0;

}