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

문제

1697번: 숨바꼭질

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

www.acmicpc.net

BFS로 풀 수 있는 문제입니다.
x - 1, x + 1, 2 * x 로 이동이 가능한데, 모두 1초씩 걸리므로, 비용이 동일하다는 것을 알 수 있습니다.
비용이 동일할 때, 최단 경로는 BFS로 구할 수 있어서 BFS로 풀이했습니다.

초기의 queue에 수빈이의 위치와 0초를 tuple의 배열 형태로 넣어주고, x - 1, x + 1, 2 * x 만큼 떨어진 곳으로 이동해야합니다.
이미 방문을 했거나, 범위 (0 ~ 10만)를 벗어난다면 이동하지 않습니다.

방문을 하지 않았고, 범위를 벗어나지 않는다면, 다음 위치와 현재 시간 + 1초를 queue에 삽입합니다.

수빈이의 위치가 동생의 위치에 도달했을 때, 시간을 출력해주면 됩니다.
x - 1, x + 1로 이동이 가능하므로 수빈이가 동생을 만나지 못하는 경우는 없습니다.

x - 1, x + 1, 2 * x 로 이동하는 것이 모든 같은 비용이기 때문에 BFS를 떠올렸고, BFS로 풀 수 있었습니다.