백준 1697번: 숨바꼭질 [python]

난이도 : 실버 1
유형 : BFS
https://www.acmicpc.net/problem/1697

문제 접근

수빈이는 현재 위치 N에 있음.
동생은 K에 있음.
수빈이는 매 초마다 다음 세 가지 중 한 가지 행동 가능:

• X - 1 (1초 후)
• X + 1 (1초 후)
• 2 * X (1초 후)

목표: N에서 K로 가는 최소 시간 구하기

이 문제를 그래프로 바라보는 관점이 핵심이다.
각 정수 좌표를 노드(node)로 보고,
이동할 수 있는 위치 (x-1, x+1, x*2)를 간선(edge)이라고 생각하면,
결국 이 문제는 정수 노드들로 이루어진 그래프 상에서 최단 거리 구하기 문제다.

즉, 그래프는 정수선, 노드는 0 ~ 100000까지의 정수
간선은 x → x-1, x+1, x*2 로 이어지는 방향 그래프임.

BFS로 푸는 이유
: BFS는 가중치가 모두 1인 그래프에서 최단 거리를 구할 때 사용한다.
이 문제에서 이동 비용은 모두 1초이므로 BFS가 적합하다.

해답 및 풀이

import sys
from collections import deque
input = sys.stdin.readline

def bfs(n, k):
    max_pos = 100001
    visited = [0] * max_pos

    queue = deque()
    queue.append(n)

    while queue:
        now = queue.popleft()

        if now == k:
            return visited[now]
        
        for next_pos in (now - 1, now + 1, now * 2):
            if 0 <= next_pos < max_pos and visited[next_pos] == 0: # 범위 걸러주고, 방문 안한 곳만 방문
                visited[next_pos] = visited[now] + 1
                queue.append(next_pos)


N, K = map(int,input().split())

print(bfs(N,K))

BFS의 힘을 볼 수 있었던 문제이다.
이렇게 활용이 되는구나.
두고두고 다시 보면서 BFS 감 떨어졌을때 찾아와야겠다.

• BFS의 특성 : 처음 도달한 값이 최단 거리