[BJ] 4179 - 불! (BFS 시작점이 두 종류)

이번엔 불과 지훈이가 동시에 있다 지훈이가 불에 타기전에 탈출을 할 수 있는지 체크를 해야한다.

 

현재 보기 TK가 4,4밖에 없으니 5,5로 예를들어 설명을 해보겠다.

열과 행이 5,5인 Board가 다음과 같이 입력이 주어졌다고 치겠다. 저번에 토마토 문제처럼 전부 거리를 -1로 만들고

지훈이 위치를 거리 0으로 만들고 시작해보자

 

지훈이의 이동 거리의 경로가 불번짐에 이동 거리보다 적기떄문에 무사히 탈출이 가능하다.

 

그럼 이렇게 그려보면 유추가 가능하다

큐를 두개(지훈,불),거리측정을 두개(지훈,불) DFS를 두번(지훈,불) 돌리고 지훈이 DFS에서 불번짐 거리를 재면 되겟구나?

범위를 벗어나면 탈출이고 큐가 빌떄까지 범위를 못 벗어나면 탈출을 못 하는구나?

 

 

여기서 중요한 포인트는 Distance가 벽도 -1인데 왜 이동이 가능하냐?

Board도 같이 조건에 벽인지 비교해주면 벽인쪽은 이동을 못하게 된다.

if (dis_jihun[x][y] >= 0 || board[x][y] == '#')
continue;

이런식으로 말이다.

Distance가 0보다 크거나 같고, Board에서 그 위치가 벽이라면? 이동을 못하게 조건을 걸어주면된다

 

그리고 지훈이는 자신이 도착한 시간과 동시에 불이 도착하거나 혹은 자신보다 더 빨리 불이 도착한다면 이동을 못하게

조건을 추가로 걸어준다.