백준 3055번 탈출

< 백준 3055번 탈출 - 마포 코딩박 >

사용한 알고리즘: BFS


 비어있는곳( . ) , 물( * ), 돌( X ), 굴( D ), 현재위치( S ) 로 구성된 grid를 주어집니다. 물이 인접한 칸으로 매분 이동할때,  현재위치에서 굴로 갈 수 있는지 묻는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드: 배열 Forest)
 초기 물이 있는 곳은 0분에 물이 차있다 생각하고 0으로 저장, 돌은 물이 퍼질 수 없으니 Infimum값으로 저장, 굴이 있는 위치는 기억하기 위해 -1 로 저장합니다.

(2) (코드: 18~29)
 물이 있는 지점이 0분에 물이 찬다고 생각하고, 이동 가능한 인접 칸들을 탐색하며 몇분에 물이 차는지 저장합니다. ( 단 돌이 있는 위치는 물이 퍼질 수 없습니다. )
 각 칸들은 가능한 물이 퍼지는 시간 중 가장 낮은 값을 저장합니다.

(3) (코드: 31~54)
 현재위치 S 에서 BFS 을 통해 굴 D 까지의 경로를 탐색합니다.
 인접 칸으로 이동할때 시간을 저장하며 탐색하고, (과정 2에서 저장해놓은) 이동할 칸의 물이 퍼진시간이 더 작은 경우는 이동하지 못합니다.

(4) 굴에 도착 가능하면 저장해간 시간을 답으로 출력하고, 굴에 도착하지 못할 시 KAKTUS를 출력합니다.