[Python] 13549번 숨바꼭질 3 (추후 보강 예정)

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

---

 

22/08/29

 

이것도 숨바꼭질 문제를 풀고 난 후 풀었던 문제이다.

 

이 문제에 대한 정확한 해설은 아직도 잘 이해하지 못한 상황이므로, 추후 보강해서 작성할 예정이다.

 

(쉽게 얘기하자면 맞았는데 아직도 정확하게 왜 맞았는지 증명을 하지 않은 상황)

 

[Python] 1697번 숨바꼭질 (tistory.com)

[Python] 1697번 숨바꼭질

---

 

접근 방법:

 

 

이 문제 또한 위의 문제와 같은데, 순간이동 할때만 1초가 아니라 0초가 걸린다고 했다.

 

맨 처음에는 큐에 넣는 순서를 그렇게 크게 신경을 쓰지 않았는데, 몇 번 제출하고 나서 틀렸습니다가 뜨니, 큐에 넣는 순서가 중요하다는 사실을 질문 게시판을 보고 알게 되었다.

 

정확한 증명은 하지 않았지만, 아마 최단시간을 찾는 것이기 때문에, 시간이 제일 짧게 걸리는(다시 말하자면 코스트가 제일 적은) 순간이동을 먼저 큐에다 넣어야만 더 먼저 그 점을 방문할 것이고, 그것이 적절한 판단이 아닐까 생각했다.

 

이런 것 처럼 가중치가 0과 1로만 된 그래프에서 빠르게 최단 경로를 찾아내는 것을 다익스트라가 아니라 BFS로 하는 방법을 0-1 BFS라고 부르는데, 이것은 추후 알고리즘을 더 배운 다음에 이 글을 더 보완하여 작성할 예정이다.

 

---

이 접근 방법을 토대로 하여 작성한 python 코드이다. 더보기를 누르면 확인할 수 있다.

# 13549번 숨바꼭질 3
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
BFS
'''
from collections import deque
N, K = map(int, input().split())

def BFS(K, start):
    if start >= K:
        print(start-K)
        return
    queue = deque([(start, 0)])
    visited = set([start])
    while queue:
        pos, time = queue.popleft()
        visited.add(pos)
        if pos > K + K-start:
            continue
        if pos == K:
            print(time)
            break
        else:
            if 2*pos not in visited:
                queue.append((2*pos, time))
            if pos-1 not in visited:
                queue.append((pos-1, time+1))
            if pos+1 not in visited:
                queue.append((pos+1, time+1))
            
            

BFS(K, N)