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

 

13549번: 숨바꼭질 3

 

문제

이동을 하여 한 지점에 도착할 때 가장 빠른 시간을 구하는 문제이다.

 

---

 

아이디어

앞으로 가는경우, 뒤로가는 경우, 순간이동하는 경우를 너비 우선탐색으로 하나씩 탐색하면 되겠다고 생각했다.

따라서 BFS를 정의하여 문제에 적용하였다.

 

---

풀이

def BFS(start):
    queue = deque()
    queue.append(start)
    visited[start] = 0

    while queue:
        target = queue.popleft()

        if target == K:
            return
        for i in (target + 1, target - 1, target * 2):
            if 0 <= i <= 100000:
                if i == target * 2:
                    if visited[i] > visited[target]:
                        visited[i] = visited[target]
                        queue.appendleft(i)

                else:
                    if visited[i] > visited[target] + 1:
                        visited[i] = visited[target] + 1
                        queue.append(i)

위와 같이 BFS를 정의하였다.

deque에 각각의 경우를 넣고 빼서 계산하였는데, 이전의 문제들과 다르게 순간이동을 할 경우 시간이 증가하지 않기 때문에 가중치를 높게 두어야 했다.

따라서 순간이동의 경우 appendleft를 사용해 deque의 가장 앞부분에 input할 수 있게 하였다.

 

이외의 구현은 visited에 MAX값을 넣어둔 후 방문 여부를 검증하였고, 방문하지 않았으면 현재 걸린 시간을 넣어 계산하였다.

---

코드

from collections import deque
import sys
MAX = 100001
N, K = map(int, input().split())

visited = [sys.maxsize] * MAX


def BFS(start):
    queue = deque()
    queue.append(start)
    visited[start] = 0

    while queue:
        target = queue.popleft()

        if target == K:
            return
        for i in (target + 1, target - 1, target * 2):
            if 0 <= i <= 100000:
                if i == target * 2:
                    if visited[i] > visited[target]:
                        visited[i] = visited[target]
                        queue.appendleft(i)

                else:
                    if visited[i] > visited[target] + 1:
                        visited[i] = visited[target] + 1
                        queue.append(i)


BFS(N)
print(visited[K])