최단 경로. [13549]

[1. 문제 설명]

수평선의 임의 시작점에서 특정 위치까지 가장 빨리 이동할 때 걸리는 시간

현재 위치 x에서 1초 후에 x-1, x+1 로 이동하거나

0초 후에 순간이동 할 경우 2x 위치로 이동할 수 있음.

 

 

[2. 풀이 접근]

다익스트라로 접근 할 필요는 없음

이동하는데 걸리는 시간은 0 아니면 1이고,

순간이동하는 경우는 같은 노드로 봐도 되므로, (x 나 2x 나 방문 순서가 같다.)

모든 edge 는 1 의 가중치를 갖는다고 볼 수 있음

따라서, bfs 로 최단 경로를 구할 수 있다.

 

1차 풀이에서 틀렸 던 점은 왼쪽으로 이동하는 경우 

x 가 음수가 될 수 있는데, 이에 대한 예외처리 (out of bound) 를 하지 않은 것이다.

 

 

[3. 코드]