[JAVA] BFS에서 Queue 대신 Deque을 사용하는 경우

BFS탐색에서 Queue로 웬만하면 해결이 되었는데 해결이 되지 않는 경우를 발견했다. 바로 가중치가 다를 때이다.

난 백준-13549(숨바꼭질3) 이 문제를 풀다가 발견하였다. 단순히 조건을 걸어 해결할 수 없었다.

• 걷기와 순간이동에 따른 시간이 달랐는데 단순히 queue에 넣어 조건을 걸게 된다면 queue의 앞쪽에서 우선 처리를 하지 않기에 최소 시간을 구하는 데 실패한 것이다.
• 이 문제의 가중치가 바로 움직임에 따른 시간변화이다.(가중치(=시간)가 다름)

=> BFS는 너비탐색이므로 시간이 같은 것부터 탐색하기에 시간이 변하지 않는 순간이동이 우선 처리되어야 한다.

<해결 방안>

• Deque을 사용한다.
  • 순간이동은 우선처리를 위해 offerFirst로 삽입한다.
  • 걷기는 offerLast로 뒤에 추가하여 시간을 수정한다.
  • 이때 단순히 offer만 사용한다면 뒤에 추가된다.