[백준] #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는 정수이다.

출력

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

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

예제 입력 1 복사

5 17

예제 출력 1 복사

4
2

---

복기

1. 골드는 아직도 많이 어렵다. 현직자 조언처럼 양치기를 더더 많이 하자.

2. 처음에 graph를 어떻게 구성해야 할지 몰라서 못 풀었다. 

if visited[next] > visited[curr] + 1:

핵심 로직중에 하나인데, curr에서 next로 갈때, 무조건 1초가 추가된다. 초기에 전부 inf로 세팅을 했는데 만약 visited[next]가 visited[curr]+1 보다 크다면 처음 방문하는 것이다.

3. q에 next를 추가해줘야 다음 curr가 여기서부터 시작이다. 추가해주지 않으면 next에 방문했다고 하고 그 이후에 탐색을 끊어버리게 되어 BFS가 중간에 멈추게 된다. 

q.append(next)

---

솔루션

from collections import deque

N, K = map(int, input().split())

max_pos = 100001
visited = [float('inf')] * max_pos
count = [0] * max_pos

q = deque()
q.append(N)
visited[N] = 0
count[N] = 1

while q:
    curr = q.popleft()
    for next in  [curr-1, curr+1, curr*2]:
        if 0<=next<max_pos:
            # 다음 위치가 처음 방문했거나, 동일한 시간에 다시 도달한 경우
            if visited[next] > visited[curr] + 1:
                visited[next] = visited[curr] + 1
                count[next] = count[curr]
                q.append(next) # q에 추가해줘야 다음 curr가 여기서부터 시작작
            elif visited[next] == visited[curr] + 1:
                count[next] += count[curr] # 이미 방문한 최소시간이므로 경로의 수만 추가

print(visited[K])
print(count[K])