[BOJ] 12851. 숨바꼭질 2(Python) / BFS

 

12851번: 숨바꼭질 2

해당 번호까지 갈 수 있는 최소 시간과 그 시간에 갈 수 있는 방법은 몇 가지인지 추가적으로 구하는 문제이다! 

예전에 숨바꼭질 1 풀었던 문제와 비슷하게 접근했는데, 추가로 구해야 하는 가짓 수 때문에 좀더 머리를 썼다.

• 사용 알고리즘 : BFS 최단 경로 알고리즘
• 먼저, K가 N보다 작거나 같다면 -1로 계속 가는 방법 뿐이다. 그러므로 N-K와 1가지 방법을 출력한다.
• 그렇지 않다면 bfs 함수를 실행해 최소 시간과 경우의 수를 구한다.
• 큐에 첫 위치 N을 담고 위치별 최소 시간을 표시하는 check 배열을 생성(-1로 초기화), N번째 위치를 0으로 표시한다.
• time은 최소 시간으로 갈 수 있는 방법의 수를 의미한다.
• while문 안에 큐의 길이만큼 for문을 돌리는 이유는 현재 턴과 다음 턴을 구분해주기 위함이다.
• 예를 들어, 거리가 3인 곳을 갈 때와 4인 곳을 갈 때를 구분해 4일 때 K에 도착했다면 해당 턴에서 K에 최소 시간으로 갈 수 있는 time을 가능한 방법의 수로 갱신된 것을 조건으로 하여 while문을 빨리 탈출할 수 있도록 하기 위함이다.
• for문 안에서 큐에서 값을 하나씩 꺼내며
  • 값을 꺼낼 때 해당 값이 K라면 가능한 방법이므로 time += 1
  • 다음 갈 수 있는 3가지 위치 nx를 큐에 담아 너비 우선 탐색한다.
  • 범위 벗어나면 continue
  • 첫 방문이거나 방문한 적이 있을 때 이동거리가 같은 경우에도, 후에 x가 K라면 time에 반영하기 위해 큐에 nx를 넣는다.
  • 새 위치에 (현 위치 + 1)한 값으로 갱신한다.
• time이 갱신되어 while문을 탈출하면 check배열의 K번째 값(최소 시간)과 time(가능한 방법의 수)을 출력한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

def bfs():
    check = [-1] * 100001
    check[N] = 0
    Q = deque([N])
    time = 0
    while time == 0:
        qlen = len(Q)
        # 이렇게 해준 이유는 time이 이번 턴에 갱신됐다면 다음 턴을 해볼 필요가 없으므로
        # 즉, 다음 턴과 구분해 while문을 빨리 나가기 위함.
        for _ in range(qlen):
            x = Q.popleft()
            if x == K:      # K에 도달할 때마다 +1
                time += 1
            for nx in (x-1, x+1, x*2):
                if not (0 <= nx < 100001):
                    continue
                # 첫 방문이거나 방문한 적 있을 때 이동 거리가 같다면 큐에 담기
                if check[nx] == -1 or check[nx] == check[x]+1:
                    check[nx] = check[x] + 1
                    Q.append(nx)

    print(check[K])     # 최소 시간
    print(time)         # 경우의 수

# main
N, K = map(int, input().split())
if N >= K:      # K가 N보다 작거나 같으면 -1로 가는 한 가지 방법 뿐
    print(N-K)
    print(1)
else:
    bfs()

---

• 시간 : 176ms / 메모리 : 131724kb
• 고찰 : 1시간 좀 넘게 걸렸다.. 어렵지 않은 문제인데 너무 많이 고민한 것 같다ㅜㅜ 블로그 한 10개 가까이 보면서 다른 사람들은 어떻게 풀었는지 감상했다. 경우의 수 구하는 것이 꽤 까다로웠다,, 비슷한 문제가 나오면 더 빨리 풀 수 있을 것 같다!