백준 12851 - 파이썬

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

12851번: 숨바꼭질 2

문제 풀이

이번 문제는 어려웠던거 같다. 숨바꼭질1 문제와 다른 점은 최단 경로의 개수도 구해야 한다는 점이다. 풀다가 도저히 모르겠어서 다른 사람의 블로그를 참고했다. 

 

코드

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

n,k = map(int, input().split())
dist = [0] * 100001

q = deque()
q.append(n)

cnt = 0
min_path = 0

while q:
  print(q)
  x = q.popleft()
  if x == k:
    min_path = dist[x]
    cnt += 1
    continue

  for next in [x-1,x+1,x*2]:
    if 0 <= next <= 100000:
      # 방문하지 않았거나 동일한 탐색 횟수를 가졌으면 탐색
      if dist[next] == 0 or dist[next] == dist[x] + 1:
        dist[next] = dist[x]+1
        q.append(next)

print(min_path)
print(cnt)

여기서 동일한 탐색횟수를 가진 곳도 탐색하는 이유는 그래야 최단경로의 개수를 탐색할 수 있기 때문이다. 만약 이 경우를 무시하게 된다면 한번 탐색한 곳은 더이상 탐색하지 않기 때문에 k와 일치하는 또다른 경우를 구할 수 없다. 또한 문제에 있는 100000이라는 범위를 지정해 둔 이유는, 이 범위 안에서 최대한 많은 경우의 수를 구하기 위함이다. 딱 한가지의 경우의 수만 구한다면 x와 k가 일치할 경우 조건문을 탈출할 것이기 때문에 상관없겠지만 이 문제는 최적의 경우의 개수 모두 구해야 하기 때문이다.

마지막으로 dist[next] = dist[x] + 1 이 코드가 이해되지 않는 경우에는 이 블로그를 참고하면 이해하는데 도움이 될 것이다.

 

느낀점

이번 문제는 정답 코드를 보고 이해하는 것도 시간이 오래 걸렸고, 동일한 탐색횟수를 가진 경우도 재탐색하여 경우의 개수를 구한다는 점도 새로웠던거 같다. 첨에 이해가 안되어 답답함도 있었지만 확실히 시간을 두고 천천히 고민해보니 이해할 수 있었다. 앞으로도 이해하기 어렵다고 낙담하는 것이 아닌 천천히 시간을 가지고 이해해 보려 노력해야 되겠다.