문제 요약

1. 수빈이와 수빈이 동생의 좌표가 주어진다.
2. 수빈이는 1초마다 현재좌표 x에서 x-1, x+1, x*2의 위치로 이동할 수 있다.
3. 수빈이는 최소 몇초의 시간이 지나야 동생을 만날 수 있을까??

접근법

이번 문제는 탐색해야하는 범위가 2차원의 형태도 아니고 1차원이다. 지금까지 2차원 BFS 문제만 풀어왔는데 처음 이 문제를 보면 BFS 문제라고 생각 못할수도 있다. 그러나 엄연히 이 문제도 BFS로 풀 수 있다. (사실 BFS로도 풀수 있다지, BFS로만 풀어야 한다는 아니다. 충분히 다른 방법도 있을 수 있다.) 오히려 탐색 범위가 줄었기 때문에 더 간단하게 풀수 있다.

이 문제는 이전에 미로탈출 문제를 1차원 형태로 바꾸고, 시작점과 끝점이 바뀔 수 있도록 변형한 문제라고 생각할 수 있다. 또 차이가 있다면 미로탈출 문제는 상하좌우로 1칸씩만 이동이 가능했다면 이 문제에서는 좌우로 1칸 이외에도 현재 위치에 2를 곱한 위치로 순간이동이 가능하다는 점이다. 만약 예제 입력처럼 수빈이가 5의 위치에 있을 때 수빈이는 1초 뒤 4, 6, 10의 위치에 있을 수 있다. 2초 뒤에는 3, 5, 6, 8, 9, 11, 12, 18의 위치에 있을 수 있다. 그러나 5와 6은 이미 방문했던 위치이기 때문에 재방문하지 않아도 된다.

위와 같이 방문했던 위치를 기록하는 배열을 1개 만들고 BFS를 수행하면 쉽게 문제를 풀 수 있다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)