[백준] 12851 숨바꼭질2 - 파이썬

문제

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

12851번: 숨바꼭질 2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

 

---

풀이

처음엔 visited를 True, False로 배열로 만들려고했는데

생각해보니까 경우의 수를 모두 구해야해서 dp + bfs로 풀어야했다.

 

visited는 True/False배열이 아니라

visited[위치][0] = 최소 시간

visited[위치][1] = 최소 시간에 위치까지 도착하는 경우의 수

 

로 바꾸어줬다.

 

종료조건은 bfs이기 때문에

최초로 k에 도달한 시간 이후의 값을 큐에서 꺼내면 while문을 탈출한다.

 

구현 하다가 헷갈려서 다른 사람 코드를 봤는데,

큰 구조는 내가 생각한 방법과 크게 다르지 않았으나

 

큐에 넣는 시점이나 종료조건이 좀 달랐다.

 

https://it-garden.tistory.com/345

백준알고리즘 - 12851번 숨바꼭질 2 - 파이썬(Python)

 

참고해서 푼 코드

from collections import deque

n, k = map(int, input().split())
dp = [[-1, 0] for _ in range(100001)]
dp[n][0] = 0
dp[n][1] = 1

q = deque([n])

while q:
    src = q.popleft()

    for i in (src+1, src-1, src*2):
        if 0 <= i < 100001:
            if dp[i][0] == -1:
                dp[i][0] = dp[src][0]+1
                dp[i][1] = dp[src][1]
                q.append(i) #왜 처음 방문했을 때에만 큐에 넣는지?
            elif dp[i][0] == dp[src][0]+1:
                dp[i][1] += dp[src][1]

print(dp[k][0])
print(dp[k][1])

 

다시 혼자 풀어본 코드

이전에 풀었을 때 왜 처음 방문했을 때에만 큐에 넣는지 의문이 있었다.

그 후에 도착하는 경우의 수도 반영이 되는 것인지 확신이 없었는데 이번에 풀어보면서 알게 되었다.

 

bfs이기 때문에 같은 시간 내에 now에 도착하는 경우의 수는 이미 계산된 후이다.

 

큐에서 꺼내는 시점에는 i에 최소 시간 내에 도착하는 경우의 수가 모두 계산된 후라는 뜻!

 

만약 elif dist[i][0]~ 에서도 큐에 추가하면

중복되어서 경우의 수가 잘못 출력된다.

 

1, 10을 넣어보면

정답: 

4

2

 

내 답:

4

16

이 출력된다.

from collections import deque

n, k = map(int, input().split())

dist = [[-1, 0] for _ in range(100001)] #0: 최단시간, 1: 방법의 수
dist[n][0] = 0
dist[n][1] = 1

q = deque([n])

while q:
    now = q.popleft()
    if now == k:
        print(dist[now][0])
        print(dist[now][1])
        break

    for i in (now*2, now+1, now-1):
        if 0 <= i <= 100000:
            if dist[i][0] == -1:
                dist[i][0] = dist[now][0]+1
                dist[i][1] = dist[now][1]
                q.append(i)
            elif dist[i][0] == dist[now][0]+1:
                dist[i][1] += dist[now][1]