✓

태그:

CLASS 4 ESSENTIAL

1697번 문제랑 비슷하기는 한데 텔레포트가 시간을 소비하지 않아서 탐색 순서를 조정할 필요가 있을 것 같아요…!!

풀이 비스무리한거 보기

1697번 - 숨바꼭질 문제와 조건은 거의 비슷하나 텔레포트에 걸리는 시간이 0초로 줄어들은 문제입니다. 기존 숨바꼭질 문제에서는 텔레포트도 걸어다니는 것과 동일하게 1초가 걸려서 단순히 BFS를 사용하면 최초로 목표에 도달했을 때 자연스럽게 최단 시간이 구해졌는데, 이 문제는 아닙니다. 만약 단순히 BFS를 사용해서 구한다면, 최초로 목표점에 도달한 상황 이후로 ceil(log<sub>2</sub> 100000)=17 정도의 깊이를 더 탐색해서 발견한 경우가 최단 시간임을 보여야 합니다. 힌트에서 주어졌듯이 탐색 순서를 조정하는 방법을 사용할 예정이라면, BFS에 사용되는 큐를 일반 큐가 아닌 우선순위 큐를 사용해서 지금까지 이동한 시간을 기준으로 정렬하는 방법도 있습니다. 0-1 너비 우선 탐색 기법도 존재하지만, 저는 잘 모르고 저 정도면 시간 제한 내에서는 충분히 해결할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-03 22:44:15

---