백준 13913. 숨바꼭질 4

tose33 2022. 12. 10. 13:48

13913번: 숨바꼭질 4

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

www.acmicpc.net

숨바꼭질 시리즈의 네번째 문제.

이번 문제는 최단거리의 경로를 출력해줘야 한다.

가장 먼저 떠오르는 가장 단순한 방법은 큐에 위치와 경로가 저장된 벡터를 저장하는 방법이다.

하지만 이 방법은 이동할때마다 벡터값을 복사해서 큐에 넣어야 하기 때문에 시간초과가 뜬다.

해결 방법은 previous 배열을 만들어 이전 좌표를 기억하는 것이다.

예를들어 현재 좌표가 x이고 다음으로 이동할좌표가 x+1 이면 previous[x+1] = x 라고 해주면, 최종적으로 도착지점에서 시작지점까지 거슬러 올라갈수 있다.