[백준/파이썬] 1697번 숨바꼭질 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1697번 숨바꼭질
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

수빈이의 현재 위치 N에서 동생의 위치 K로 이동할 때, 가능한 이동은 -1, +1, *2 세 가지입니다.

한 번 이동할 때마다 시간이 1초 걸릴 때, 동생을 찾는 최소 시간을 구하면 됩니다.

코드

from collections import deque

Q = deque([])
enQ = Q.append
deQ = Q.popleft

n, k = map(int, input().split())
enQ((n, 0, set()))

while Q:
    pos = deQ()
    pos[2].add(pos[0])
    if pos[0] == k:
        print(pos[1])
        break
    if pos[0] > 0 and pos[0]-1 not in pos[2]:
        enQ((pos[0]-1, pos[1]+1, pos[2]))
    if pos[0] < 100000 and pos[0]+1 not in pos[2]:
        enQ((pos[0]+1, pos[1]+1, pos[2]))
    if pos[0] <= 50000 and pos[0]*2 not in pos[2]:
        enQ((pos[0]*2, pos[1]+1, pos[2]))

설명

가능한 이동을 동일 가중치(1초) 간선으로 보면 그래프 최단거리 문제입니다.

• 큐(deque)를 이용한 BFS로 탐색합니다.
• 상태는 (현재 위치, 누적 시간, 방문 집합)으로 관리합니다.
• 목표 위치 K에 처음 도달한 시점의 시간이 최소 시간입니다.

---

• 백준 문제풀이 전체 목록 보기

---