[BOJ] 백준 13913 숨바꼭질 4 (Swift)

문제

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

풀이

X에서 X - 1, X + 1, 2 * X 의 방향으로 이동하는 경우 모두 1초가 걸리기 때문에,
BFS로 최단비용를 구할 수 있습니다.

최단거리로 간 루트를 구하기 위해 visited라는 Int 배열을 선언하였습니다.
이 Int 배열의 index를 현재 위치, 값을 이전 위치로 사용하려고 합니다.

예를들어 visited[10] = 9 라면, 9에서 출발하여 10을 도착한 것 입니다.

그렇다면 동생의 위치에서 부터 수빈이의 위치가 될 때까지 반복해서 루트를 찾아줄 수 있습니다.
수빈이의 위치에서 동생의 위치까지의 경로를 출력해주기 위해서 배열을 뒤집어주었습니다.

소스코드

후기

BFS와 경로를 역추적 하는 문제였습니다.
최단비용을 구하는 것은 쉽게 떠올렸고, 경로를 구하기 위해 Int 배열을 활용하는 것은 조금 생각해서 풀이했던 문제였습니다.