[BOJ] 1697번: 숨바꼭질(python)

문제 링크 : https://www.acmicpc.net/problem/1697

💡 해결 방법

• visited 리스트는 N부터 시작해서 인덱스의 숫자에 도달했을 때의 count를 담고 있다.
• 최상위 노드 N부터 시작해서 N-1, N+1, N*2 세 개씩 각 노드별로 뻗어나가는 모양의 그래프를 하고 있다.
• 예를 들어, 현재 위치가 5라면, 4,6,10의 위치에 모두 1을 표시하는 것이다.
• 이를 반복하여 해당 위치로 갈 때마다 몇 번 이동을 해야 하는지 추가한다.

정답코드 참조

🖥️ 코드

import sys
from collections import deque

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

MAX = 100001
N, K = map(int, sys.stdin.readline().split())
visited = [0] * MAX
print(bfs(N))

✏️ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색