문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
알고리즘
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색(bfs)
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
입력 예
5 17출력 예
4입출력 예에 대한 설명
수빈이가 5 → 10 → 9 → 18 → 17 순으로 가면 4초만에 동생을 찾을 수 있다.
풀이
이 문제에는 BFS(너비 우선 탐색) 알고리즘을 적용했다.
A부터 B까지의 최단경로를 구하는 이 문제에는 BFS가 적합하다고 판단했다.
DFS(깊이 우선 탐색)
BFS(너비 우선 탐색)
그림 출처 - https://developer-mac.tistory.com/64
수빈이는 1초에 현재 위치 + 1 or - 1, or * 2 만큼 이동할 수 있다.
그러므로 시작 위치가 5라면
1초에 갈 수 있는 곳 - 4, 6, 10
2초에 갈 수 있는 곳 - 3, 5, 8, 7, 12, 9, 11, 20
3초에 갈 수 있는 곳 - 2, 16, ・・・, 18, ・・・
4초에 갈 수 있는 곳 - 1, ・・・, 17, ・・・
1초에 갈 수 있는 곳인 4, 6, 10의 정보를 리스트에 기록한다.
ex) [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1]
4, 6, 10에서 각각 갈 수 있는 곳을 조사한다.
2초에 갈 수 있는 곳이니까 리스트에 2라고 표시한다.
이때 이미 그 자리에 0이 아닌 다른 숫자가 있다면 pass한다.
코드
from collections import deque
def bfs(MAX, start, target):
dist = [0] * (MAX + 1)
q = deque()
q.append(start)
while q:
x = q.popleft()
if x == target:
return dist[x]
for i in (x - 1, x + 1, x * 2):
if 0 <= i <= MAX and not dist[i]:
dist[i] = dist[x] + 1
q.append(i)
MAX = 100000
N, K = map(int, input().split())
print(bfs(MAX, N, K))코드 설명
-
위의 정보를 담을 dist 배열을 선언하고 주어진 최대값(10만) 만큼 0으로 초기화한다.
-
python 라이브러리인 deque를 선언한다. 한방향에선 입력만 가능하고 다른 방향에선 출력만 가능한 일반적인 queue와 다르게 deque는 쌍방향에서 입출력이 가능한 자료구조이다. 초기값은 처음 시작하는 숫자(5)로 정한다.
-
무한 반복문을 돌리고 x에 deque의 맨 왼쪽에 있는 숫자를 대입한다.(popleft)
-
x - 1, x + 1, x * 2 세 경우를 조사한 뒤 나온 값이 범위를 벗어나지 않고 dist에 기록 되어있지 않다면 dist에 기록하고 deque에 그 값을 집어넣는다.
-
deque에서 나온 값이 목표값과 일치한다면 dist에서 값을 꺼내 return
