[백준] 1697 숨바꼭질 (python)

문제 링크

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

접근법 및 사용 알고리즘

문제 내 point

• "가장 빠른 시간" -> BFS 사용해야겠구나!
• x+1, x-1, 2*x 와 같이 x축의 움직임만 존재 -> 1차원

코드

from collections import deque

n, k = map(int, input().split())  # n: 수빈이의 위치, k: 동생의 위치
MAX = 10**6+1
arr = [0]*MAX

def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if v == k:
            return arr[v]
        for next in v-1, v+1, 2*v:
            if 0 <= next < MAX and not arr[next]:
                arr[next] = arr[v]+1
                q.append(next)

print(bfs(n))

흐름 이해하기

초기 상태

• 시작 위치 n = 5, 목표 위치 k = 17
• 초기 큐 q = deque([5])
• 초기 배열 상태 : arr = [0,0,0,...,0]

첫 번째 반복

• popleft()로 v = 5를 이용해 계산 시작
• 5에서 갈 수 있는 위치 4, 6, 10 (각각 5-1, 5+1, 2*5한 값)
• 큐에 추가하기 q = deque([4, 6, 10])
• 배열 업데이트 arr[4] = 1, arr[6] = 1, arr[10] = 1 (이전에는 5를 방문한 적 없었기 때문에 arr[5] = 0에서 +1된 값으로 갱신)

계속 반복

• popleft()로 맨 앞부터 꺼내어 첫 번째 반복과 같은 흐름 반복

채점 결과

유사 문제 : 백준 5014 스타트링크
https://www.acmicpc.net/problem/5014