[c++] 백준 불!(4179), BFS, 반례모음

문제 https://www.acmicpc.net/problem/4179

• J와 F(불)이 미로에 있음.
• J는 F를 피해 미로를 빠져나와야 한다. 미로 밖으로 나오면 성공

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

J가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

풀이

• 맵에서의 J와 F의 좌표를 모두 큐에 쌓고, 하나씩 BFS를 이용해 인접한 좌표로 이동한다.
• 핵심은 조건문을 통한 예외처리가 아닐까 싶다.
• 특이사항
  - 불이 여러개일 수 있음.
  - J가 벽에 갇힐 수도 있음. 
• 맵을 문자열로 구성하고, J나 F가 이동시에 현재 좌표에 새로 할당해준다. 
  - J의 이전좌표는 '.'으로 표시, F의 모든 좌표는 지우지 않는다. 
• J의 이동거리와 방문했는지 여부를 판단할 수 있는 map_check를 map가 동일한 크기로 만든다.
  - J가 이동하면 +1씩 더해서 업데이트 해준다. 0인 곳만 방문을 하지 않은 것이다. 
  - 방문여부 체크를 하지 않으면 메모리 초과 오류가 발생 (이것때문에 정말 고생했따.)
• map에 있는 문자(#,J,F, . )과 map_check에 있는 이동거리를 이용해 조건문 처리를 수행하여 결과를 내놓는다.
• 주어진 반례가 1개밖에 없으므로 아래 여러 가지를 추가하였음.
• 개인적으로 현재 map의 상태를 계속 출력해서 J,F가 의도한대로 이동 및 업데이트 하는지 확인하는게 더 빨리 문제를 해결할 수 있다.

 

반례모음

3 4 ##.# FJ.# ##F# ans : IMPOSSIBLE	5 5 FFFFF ..J.. ..... ..... ..... answer:4	4 4 #### #J## ##F. ##.# IMPOSSIBLE	4 4 #### #JF# #..# #..F IMPOSSIBLE
4 4 #F## #F## ..J# #### IMPOSSIBLE	5 5 #F..# #.J.# ###.# ###.# ###.# 5	5 5 ##### #F#J# ###.# ###.# ###.# 4	2 2 JF FF 1

4 102 ###################################################################################################### #J.................................................................................................... #F.................................................................................................... ###################################################################################################### 101

 

코드

 

알게 된 점

• 조건문 예외처리는 빡세다..
• 반례 생각도 쉽지 않다..
• 어쩌면 코테란 위의 2가지가 제일 중요할지도..?

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EB%B6%88(4179).cpp