[Python] 백준13549 숨바꼭질 3

27 May 2023 in Study on Algorithm

백준13549 숨바꼭질 3 링크

문제

예제 입력

---

코드

from collections import deque

n, k = map(int, input().split())
arr = [float("inf")] * 100001

def bfs(st):
    q = deque()
    q.append(st)
    arr[st] = 0
    while q:
        pos = q.popleft()

        if 0 <= pos * 2 <= 100000 and arr[pos*2] > arr[pos]:
            arr[pos*2] = arr[pos]
            q.append(pos*2)
        if 0 <= pos - 1 <= 100000 and arr[pos-1] > arr[pos] + 1:
            arr[pos-1] = arr[pos] + 1
            q.append(pos-1)
        if 0 <= pos + 1 <= 100000 and arr[pos+1] > arr[pos] + 1:
            arr[pos+1] = arr[pos] + 1
            q.append(pos+1)

bfs(n)
print(arr[k])

설명

파이썬을 통해서 사용자로부터 입력받아 BFS알고리즘을 사용하여 숨바꼭질 3를 구현했습니다.
모든 경로 비용이 1이라면 단순 BFS으로 한번에 해결 가능하지만, 이 문제의 경우 비용이 0, 1 인 경우 두가지가 있기 때문에 BFS탐색중에 이미 방문한 지점이라도 이전보다 더 적은 비용으로 방문 가능한 경우가 있습니다.
따라서 BFS 탐색시에 해당 지점까지 더 적은 비용으로 도착 가능하다면 더 적은 비용으로 갱신해 주어야 합니다.

---

결과