BAEKJOON_3055) 탈출

BAEKJOON 

# 2019 SW역량테스트준비-기초

# 그래프와 BFS # BFS 2

3055) 탈출 (19.09.26)

* BFS사용.
* 우선 물이 차는 시간을 go배열에 입력하기 위해서 물이 차있는 공간(*)을 list에 추가.
* list에 저장된 곳(시작점)에 0넣고, 돌(X)과 도착지(D) 빼고 물이 차는 시간을 적어줬다.

* 처음에는 go배열 그냥 썼는데, 문제 다 풀고 고치다보니까 -1로 초기화 해줬다.
* go에 물 다 채우고 -1인 곳은 물이 지나가지 못한 공간이다.
* 고슴도치 경로를 ans에 넣을 때,
* 물 차는 시간과 고슴도치 시간을 비교해서 물이 더 늦게 차면 고슴도치가 지나가는데,
* -1칸인 것 중에 목적지가 있기 때문에, 고슴도치가 지나가려면
* -1을 제외하고 물이 차는 시간과 비교해야 한다(line 94).
* 이때는 돌도 -1이라서 돌도 제외한다는 부분을 추가(line 93).

* 이거때문에 계속 답이 안나왔었는데,
* line 94에 물이 차는 시간을 비교하는 부분에서 ans[u][v]와 go[u][v]를 비교했었다.
* 이건 다음칸인 ans[u][v]의 값이 아직 정해지지 않았기때문에 저렇게 하면 안되고,
* 지금칸인 ans[x][y]에 1을 더한 값이 다음칸의 값이니까 이거랑 비교해야한다.

* 그리고 마지막에는 목적지에 적힌 숫자를 출력, 0이면 고슴도치가 못간거니까 실패문구 출력

* Pair랑 큐, 리스트를 잘 쓸수 있게 된거 같당.