백준 1697
수빈이가 동생을 찾는 가장 빠른 시간 구하기.
- 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
- 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
- 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
- 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
- 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
입출력
| 입력 | 출력 |
|---|---|
| 5 17 | 4 |
접근 방식
: bfs이용. dx = ['-1', '+1', '*2']로 설정해두고, 해당 위치에서 dx의 값들을 연산한 값이 k가 아니라면 큐에 넣는다.
알게된 점
맥락은 비슷하다. bfs를 이용하는데 이 때 가지 않았던 좌표만 탐색해야 하므로 이를 기억할 visited를 추가한다. visited는 방문여부와 그 거리까지의 걸린 시간을 함께 저장하는 역할을 한다.
문제에서 점이 100000까지이므로 visited의 원소를 100001개로 두고 모두 0으로 초기화해둔다.
nx는 현재 지점x에서 -1, +1, *2를 한 값인데 이 값의 범위가 100000를 넘지 않아야하고, 방문하지 않았다면 이에 해당하는 visited값을 x의 visited의 값+1로 업데이트 한 후 큐에 넣는다.
코드
from collections import deque
def bfs(n, k, visited):
q = deque()
q.append(n)
while q:
x = q.popleft()
if x == k:
return visited[x]
for nx in (x-1, x+1, x*2):
if 0<=nx<=100000 and visited[nx]==0:
visited[nx] = visited[x] + 1
q.append(nx)
n, k = map(int, input().split())
visited = [0]*100001
print(bfs(n, k, visited))