불!
Prob
나무 섭지와 유사
J 출발
# 벽
F 불
. 통로
불을 피해서 출발지에서 미로의 가장자리로 통과하면 가장 빠른 탈출시간 출력 못하면 IMPOSSIBLE 을 출력 불도 벽 통과 못함
Solv
미로의 가장자리로 통과해야하니 주어진 행 R, 열 C 보다 2칸 크게 map 설정
불을 위한 map2로 먼저 가장자리까지 도달하기 위한 최단거리 파악
지훈을 위한 map으로 가장자리까지 도달 시 불보다 작으면 탈출시간 출력 그렇지 않다면 IMPOSSIBLE 출력
Check
기본사항
불의 최단거리 파악을 후 지훈의 최단거리가 해당 지점에서 불보다 작은지 파악하는 것으로 풀이 가능
5 5
FFFFF
..J..
.....
.....
.....
정답 4
예외사항 1
불이 없는 경우 지훈이 가장자리 도달 시 불보다 작을 수 없음
-> 가장자리 초기값을 위한 MAX 설정
6 5
##.##
#...#
#...#
#...#
#J..#
#####
정답 6
예외사항 2
가장자리에서 불이나 지훈이 map에 최단거리 업데이트 후 dq에 추가되면 안됨
가장자리는 도착지이게 때문에 bfs 수행 시 옆 통로로 들어가 에러 발생
7 7
#######
#J#####
#.....#
#.#.#.#
#.#.#.#
F.#.#.#
##F.#.#
정답 10
Feedback
기본 알고리즘 작성 후 예외사항에 대해 생각하고 처리하자.
예외 케이스는 Q&A를 참고했지만 스스로 문제를 보고 파악하도록 해보자.
