BOJ(숨바꼭질2)(12851)

작성일 | In

숨바꼭질2 12851

  • 수빈이의 위치 : N
  • 동생의 위치 : K

  • 동생을 찾는 가장 빠른 시간을 구하는 문제, 그리고 그러한 방법의 개수도 구해야 한다.

  • 수빈이가 할 수 있는 행동 (위치 :X)
  1. 걷기: X+1 또는 X-1로 이동(1초)
  2. 순간이동 : 2*x로 이동 (1초)
  • 앞에서 본 숨바꼭질 4
  • 5->17로 간다면 5 -> 10 -> 9 -> 18 -> 17로 이어지는 최소방법을 구하는 문제였다.

  • 숨바꼭질 2는 최소를 구하는데, 그러한 방법의 개수도 구하는 문제다.

  • 가장 빠른 시간을 구하는 건 BFS인데, 그러한 방법의 개수는 ? -> Dynamic

  • Cnt[i] = i까지 가는 방법의 개수
  • cnt의 i, 10은 아직 방문하지 않음, 11도 아직 방문하지 않음.
  • (이미지 : 5->10, 9->10, 11->10)
  • 5와 9까지의 거리는 3이라고 하면,
  • 5에서 10을 갈 수 있다면 무조건 10 방문
  • 5까지 가는 방법의 개수는 10까지 가는 방법의 개수와 같다는 것을 알 수 있다.

  • 그런데 10까지 가는 게 5와 9에서 가는게 가능하므로, 둘다 최소가 되니까, 10까지 가는 방법에 9까지 가는 방법을 더해줘야 한다.

  • 똑같은 BFS인데,
else if (dist[next] == dist[now] +1){
    cnt[next] += cnt[now];
}
  • 위 코드가 추가된다.
  • 무조건 더하는게 아니라, 어떤 3개의 정점이 있는데, 여기까지의 최소 거리가 2,2,3,2였다고 한다면, A,B,D를 방문했다고 하면, C->D로 방문할 수 있는데, d를 이미 방문했다면. 더하면 안된다.
  • 다음까지의 거리가 현재까지의 거리 +1이 된다.
from collections import deque
MAX = 200000
check = [False]*MAX
dist = [0]*MAX
cnt = [0]*MAX
n,m = map(int,input().split())
check[n] = True
dist[n] = 0
cnt[n] = 1
q = deque()
q.append(n)
while q:
    now = q.popleft()
    for next in [now-1, now+1, now*2]:
        if 0 <= next < MAX:
            if not check[next]:
                q.append(next)
                check[next] = True
                dist[next] = dist[now]+1
                cnt[next] = cnt[now]
            elif dist[next] == dist[now]+1:
                cnt[next] += cnt[now]
print(dist[m])
print(cnt[m])

참고자료 codeplus

0%