[탐색/BFS] 백준 13549 숨바꼭질 3 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

13549번: 숨바꼭질 3

 

 

 

2. 문제 풀이

  수빈이는 1초 후에 X-1 또는 X+1로 이동할 수 있으며, 2*X로의 순간이동에는 시간이 소모되지 않습니다. K 위치에 있는 동생에 도달하는 가장 짧은 시간을 구해야 합니다.

 

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

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

 숨바꼭질 문제에서, '2*X' 이동의 가중치가 0으로 바뀌었습니다. 따라서, 우선순위를 2*X 이동으로 앞당겨줘야 합니다.

 

 

 

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]:
            if nextX == x*2:
                dist[nextX] = dist[x]
            else:
                dist[nextX] = dist[x] + 1 #방문하고 횟수 1늘림
            queue.append(nextX) #큐에 추가

 x*2 이동이 큐에 먼저 들어가야 하므로, 위와 같이 코드를 짜면 틀립니다.

 

 

 

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*2, x-1, x+1):
        # 0~100000지점 내이고, 방문하지 않았다면
        if 0 <= nextX <= 100000 and not dist[nextX]:
            if nextX == x*2:
                dist[nextX] = dist[x]
            else:
                dist[nextX] = dist[x] + 1 #방문하고 횟수 1늘림
            queue.append(nextX) #큐에 추가

 X*2부터 먼저 탐색해야 맞습니다.