[BOJ] 1697번 숨바꼭질 - Python

문제

1697번: 숨바꼭질

 

 

풀이

• 가중치가 있는 그래프에 대한 처리를 어떻게 하면 좋을지 고민할 수 있었던 문제
• 일차원 배열이어도 접근 방식은 비슷하다.
• 무게나 비용이 가장 적은 것 먼저 넣고 그것들을 먼저 뽑고 싶기에 큐를 사용했던 것이다, 가중치가 있으면 이를 만족하는 것이 맞다.
• 해당하는 자료구조가 왜 등장했는지 생각하자.

from collections import deque


def solution(n, k):
    if n == k:
        return 0

    size = 200000
    d = [-1] * size

    queue = deque()
    queue.append(n)
    d[n] = 0  # visited 와 동일

    while queue:  # 조건
        x = queue.popleft()
        nx = x * 2  # 시간이 들지 않기 때문에 가장 적은 비용, 가장 먼저 큐에 들어 가야 함, 그래야 방문할 수 있는 가장 작은 값이 저장됨 (가중치가 있는 그래프임을 기억)
        if nx < size and d[nx] == -1:
            queue.append(nx)
            d[nx] = d[x]
        nx = x - 1
        if 0 <= nx < size and d[nx] == -1:
            queue.append(nx)
            d[nx] = d[x] + 1
        nx = x + 1
        if 0 <= nx < size and d[nx] == -1:
            queue.append(nx)
            d[nx] = d[x] + 1
    return d[k]


N, K = map(int, input().split())
print(solution(N, K))