13913 숨바꼭질 4

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

평범한 BFS를 적용하면 최단횟수는 쉽게 구할 수 있으므로

BFS 구현 내용은 적지 않는다

BFS 역추적 방법

분기점은 3갈래로 나뉘므로, 부모 기준으로 자식이 3개 생기는 트리와 비슷하다

해를 찾았을 때, 해로부터 Root로 가는 경로는 유일하다

직관적인 이해를 위해서 이미지화 하면 위와 같은 그림이 된다

- BFS 탐색시, parent 배열을 통해서 해당 정수의 부모 정수를 기록해준다

- 해를 찾았다면 parent 배열을 통해 부모를 거슬러 올라갈 때마다 경로를 기록해준다

- Root에 도달하면 종료한다

시간 줄이는법

일반적인 BFS 구현으로 푼다면 아무리 최적화를 해도 1000ms 이상 나올 것 이다.

N >= K 일때의 극단적인 저격테케 때문이다.

N >= K 인 경우를 따로 분리해내서 처리를 해준다면 시간을 크게 줄일 수 있다.

김심야 팬