[Python] 12851번 숨바꼭질 2

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

12851번: 숨바꼭질 2

---

 

22/08/29

 

숨바꼭질 문제를 풀고 난 후 시리즈로 있길래 바로 풀어본 문제이다.

 

숨바꼭질 코드에서 약간의 수정만 거쳤으며, 기본 베이스가 되는 아이디어는 숨바꼭질 문제와 같다.

 

https://lighter.tistory.com/15

[Python] 1697번 숨바꼭질

---

접근 방법:

 

 

문제 자체가 위의 문제와 같고, 단지 경로의 가짓수를 찾는 과정이 추가되었다.

 

일단, 나는 is_break라는 플래그를 하나 세워야겠다고 생각했다.

 

왜냐하면 최단 경로를 하나 찾는 그 순간, 큐에 더 이상 원소를 추가하지 못하도록 하기 위함이었다.

 

큐에 원소를 추가하면 추가할수록, 항상 그 원소는 이전 원소보다 시간이 +1 커진 상태로 추가가 된다는 사실을 알 수 있다.

 

때문에, 최단 경로를 하나 찾으면, 그 뒤로부터는 이 플래그를 통해 큐에 원소를 추가하지 못하도록 했다.

 

또한, 숨바꼭질 1 문제를 풀 때와 마찬가지로, 큰 쪽에서 작은 쪽으로 가는 방법의 수는 항상 한 가지로 정해져 있기 때문에 그것 또한 미리 가지치기로 빼두었다.

 

이후 최단 시간으로 도착하는 경로가 나올 때마다 times라는 리스트에 최단 시간을 append 하여 나중에 그 리스트의 길이만을 반환하는 형식으로 최단 경로의 가짓수를 구했다.(어차피 times 리스트에는 항상 같은 숫자만 추가된다)

 

---

이 과정을 겪어서 제출한 나의 코드이다. 더보기를 누르면 확인할 수 있다.

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

def BFS(K, start):
    is_break = False
    times = []
    if start >= K:
        return start-K, 1
    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:
            if times == []:
                times.append(time)
                is_break = True
            else:
                if times[0] == time:
                    times.append(time)
        else:
            if not is_break:
                if pos+1 not in visited:
                    queue.append((pos+1, time+1))
                if pos-1 not in visited:
                    queue.append((pos-1, time+1))
                if 2*pos not in visited:
                    queue.append((2*pos, time+1))
    return times[0], len(times)

time, method = BFS(K, N)
print(time)
print(method)