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

문제 설명

---

풀이 코드

숨바꼭질 3번 문제와 완전 똑같은데 순간이동시 시간이 1초 소요된다는 점만 다르다.

[Python/파이썬] 백준 13549 - 숨바꼭질3

 

1. 동생의 위치 k에 도달할 때 까지 문제에 주어진 3가지 이동방법으로 탐색한다.
2. 문제에 주어진 범위 0 <= N <= 100,000안 일 경우 탐색하도록 한다.
3. 순간이동을 많이 쓰는 방법이 가장 빠르게 도착하는 방법으로 순간이동은 appendleft()로 먼저 탐색하도록 한다.
4. 동생의 위치 k에 도달하면 도착 시작 값을 반환한다.

 

정답 코드

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

n, k = map(int, input().split()) # 수빈이의 위치, 동생의 위치

def bfs(n, k):
    visited = [-1] * 100001 
    visited[n] = 0
    q = deque([n])

    while q:
        cur = q.popleft()

        if cur == k:
            return visited[cur]

        # 동생의 위치에 도달할 때 까지, 3가지의 이동 경우를 확인 (x + 1, x - 1, x * 2)
        for next in (cur + 1, cur - 1, cur * 2):
            if 0 <= next <= 100000 and visited[next] == -1:
                if next == cur * 2:
                    visited[next] = visited[cur] + 1
                    q.appendleft(next) # appendleft()로 순간이동을 먼저 탐색
                else:
                    visited[next] = visited[cur] + 1 # 걸어서 이동은 1초 소요
                    q.append(next)
print(bfs(n, k))