[BOJ3055] 탈출

고슴도치가 굴로 들어가기 위한 최소 시간

• 지도 R * C
• 빈 공간 ‘.’ / 물 ‘*’ / 돌 ‘X’ / 비버 굴 ‘D’ / 고슴도치 ’S’
• 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동 가능
• 물은 사방으로 확장
• 고슴도치와 물은 돌은 통과 못 함
• 고슴도치는 물 못 감
• 물은 고슴도치 굴 못 감
• 숲지도 주어졌을 때, 고슴도치가 굴로 이동하기 위한 최소 시간
• 고슴도치는 물이 찰 예정인 칸으로 못 감

입력

• 첫째 줄 R, C (<= 50)
• 다음 R개 줄에 지도

출력

• 고슴도치가 굴로 이동하는 가장 빠른 시간 출력
• 안 된다면 “KAKTUS” 출력

설계

• 홍수 / 고슴도치 BFS 두 개 사용
• 큰 틀은 고슴도치 큐를 이용해서 계속 반복
• 큰 틀 안에 홍수 큐 사이즈만큼 반복, 고슴도치 큐 사이즈만큼 반복
• 고슴도치는 맵에서 하나씩 옮기기보다 홍수처럼 사방으로 퍼뜨리는 방식으로해도 결과 성립
• 맵의 특정 값이 ‘.’일 때에만 홍수, 고슴도치 움직이도록
• ‘D’ 만나면 종료 후 퍼진 날짜 출력, 못 만나면 ‘KAKTUS’ 출력

How I solved(click to github)

---

ref :
BOJ3055