[백준 알고리즘][BFS] 5427번 불, 4179번 불!

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력과 출력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

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

풀이

불이 번지는거보다 빨리 탈출해야 하는데..어려운거같다. 최단경로는 불이 없다고 치면 그냥 BFS단계의 수랑 같을 텐데 문제는 불이 번져나가고 있으니까 가는 길에 불이 있으면 안된다. 그래서 생각한건 BFS를 동시에.. 두개를 해서 불도 계속해서 visited 배열을 통해 만약 불이 지나가면 못가게 되는거다. 근데 말로는 쉬운데 BFS를 동시에..하려면 큐를 두개 만들어서 가능하려나? 한 단계씩 해나가면 되니까? input을 통해서 visited 배열을 만들어서 벽은 true로 해두고, 불은 false 에서 true로 바꾸며 첫번째 큐에 넣어서 시작한다 두번째 큐에는 상근이의 위치에서 시작해서 BFS를 한다. 어차피 한 단계씩 이루어지므로 불이 번지도록 방문을 먼저 하고 상근이도 빈공간을 방문하도록 한다. 주어진 예제는 다 잘 돌아가는데 틀렸습니다가 나온다... 질문검색에 있는 테스트케이스도 다 돌아가게끔 고쳤는데 50%에서 틀린다.

+추가 2019.01.25

이 문제랑 유사한 4179번 불! 문제를 풀고 해당 코드에서 그대로 이 문제 조건에 바꿔주니 맞았습니다를 받았습니다. 풀이 방법은 위에서 언급한 부분이랑 거의 비슷했습니다. 큐를 2개 만들어서 사람이 이동하는 경로와 불이 이동하는 경로를 넣어줬습니다. 큐에 계속해서 반복되는 좌표를 넣어주지 않으면서 방문한 곳은 방문하지 않아야 하고 사람이 이동한 경로에는 불이 이동할 수 있지만 불이 이동한 경로엔 사람이 더이상 이동할 수 없도록 해줘야합니다. move.pop() 했을 때 해당하는 값이 그 전 step에서 불이 퍼진 경로가 아니어야 해당하는 경로에서 퍼져나갈 수 있도록 해줘야합니다. visited 배열을 여러개 둘 필요 없이 0, 1, 2, 3을 통해서 적절히 조절해주니 맞았습니다!

제출한 시간과 이 글을 작성했던 날을 보니 2018년 1월 24일에 이 문제를 풀었었는데 그 이후로도 틀렸다가 오늘은 처음에 생각을 떠올린대로 코드를 작성하니 바로 맞았습니다. 1년이라는 기간동안 꽤 많은 문제를 풀면서 좀 더 실력이 늘고 있는 것 같아서 뿌듯하다는 생각이 들었습니다!

코드

4179번 불! : https://github.com/kswim/Algorithm/blob/master/BFS/4179.cpp