A. 문제설명
https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제��
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. R*C 배열크기 땅이 존재
2. 각 배열의 엔트리에는 빈칸, 물, 비버굴, 돌이 존재
3. 고슴도치는 주어진 위치에서 물과 돌을 피해 빈칸을 이동하며 비버굴에 가고자 함
4. 물이 고슴도치를 덮치기 전에 가장 빨리 비버굴에 갈 수 있는 시간을 구하라
B. 접근법
Double BFS
일반적인 배열 주변 영역 전파 문제에서는 BFS를 쉽게 적용할 수 있다. 그러나, 이 문제에서는 다시 한번 생각을 해야한다.
먼저, 문제에서 크게 고려해야 할 것은 두가지이다. 1) 매 초마다 주변으로 퍼지는 홍수(물), 2) 물을 피해 매 초마다 빈칸으로 이동하여 비버굴로 도망치는 고슴도치
여기서 물과 고슴도치는 둘다 BFS로 주변 지형에서 갈 수 있는 공간을 모두 탐사해야 한다.
물의 경우, 갈 수 있는 공간을 모두 채워가며 탐사하므로 BFS로 매 초마다 빈공간을 물로 채워가며 이동하고, 비버의 경우 탐색가능한 모든 경우를 찾아가며 최적의 경로를 확인하여야 한다.
여기서 BFS를 이중으로 적용할 때, 규칙을 임의로 정하면 혼동을 피할 수 있다.
1. 비버가 갈 수 있는 모든 경로를 탐색할 때까지(큐가 빌 때까지) BFS 탐색
2. 비버가 먼저 가고, 물이 이동. 여기서, 비버가 이동한 위치에 물이 덮친다면 그 위치는 비버가 갈 수 없는 위치가 된다.
3. 2번에서 물이 이동하여 비버의 위치를 물로 덮는다면, 해당 위치는 유효하지 않게 판단
위 세가지를 잘 염두하여 구현에 그대로 녹여내어 보자.
C. 풀이
1. escape() 함수는 Double BFS로 매 초를 증가시키며 고슴도치 -> 물 순으로 이동
2. 전체 반복 조건은 고슴도치 큐가 빌 때까지
3. 먼저 고슴도치가 주변 영역중 갈 수 있는 영역으로 이동(범위 안, 돌 X)
4. 만약 고슴도치가 비버굴을 발견하면 종료하고 시간을 최소에 업데이트
5. 물은 BFS로 지도를 칠하며 영역을 넓혀나감
6. 비버가 있는 위치를 만나도 위에 덧칠함
D. 내 코드
