[탐색/BFS] 백준 1697 숨바꼭질 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1697번: 숨바꼭질

 

 

 

2. 문제 풀이

 출발 지점 N에서 도착 지점 K까지 가장 빠르게 가는 방법을 찾는 문제입니다.

 

1) X - 1
2) X + 1
3) 2 * X

 

 3가지 방법으로 움직일 수 있고 최대한 적게 이동해서 도착해야 합니다. 1차원 그래프이기 때문에, 처음에는 DP문제인 줄 알았습니다. 하지만 DP처럼 모든 경우를 탐색할 순 없으며, 그럴 이유도 없습니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 그래프 탐색 기법을 이용해서 시작점에서 도착점으로 가는 루트를 찾아냅니다.

 

 

 굳이 그래프로 표현하자면, 위와 같습니다. 그렇다고 일일이 그래프 정보를 기입할 필요는 없고, 탐색방법만 위 3가지에 따라서 해주시면 됩니다.

 

 

 

3. 코드

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

N, K = map(int, input().split()) #출발 / 도착
dist = [0] * 100001 #최대 0부터 100000까지의 지점까지 걸리는 횟수 기록

#BFS 탐색
queue = deque()
queue.append(N) #시작점

# 큐가 빌 때까지 탐색
while queue:
    x = queue.popleft()
    # 도착지점이라면 탐색 종료
    if x == K:
        print(dist[x])
        break
    # x에서 -1 또는 +1 또는 *2 탐색
    for nextX in (x-1, x+1, x*2):
        # 0~100000지점 내이고, 방문하지 않았다면
        if 0 <= nextX <= 100000 and not dist[nextX]:
            dist[nextX] = dist[x] + 1 #방문하고 횟수 1늘림
            queue.append(nextX) #큐에 추가

 각 지점이 노드가 되며 최대 100000개입니다. 각 노드에 저장할 데이터는 '출발지에서 해당 노드까지 걸린 횟수'이며, DP테이블과 유사합니다.

 -1, +1, *2를 하며 BFS로 도착지를 탐색합니다.