[백준 12851] 숨바꼭질2 -Python 풀이 (골드4)

문제

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

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

입력

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

출력

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

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

---

풀이

숨바꼭질 문제와 유사한 문제이다. 

https://bongseok.tistory.com/31

[백준 1697] 숨바꼭질 (실버 1) Python

 

마찬가지로 BFS로 각 계산 결과를 정점으로 하여 탐색을 진행한다. BFS 함수 내에서, 만약 K 값에 도달하면 최단 시간을 업데이트해주고, 해당 경로가 최단 경로일 때에는 최단 경로를 업데이트해준다. 일반적인 BFS와 달리, 다음 정점을 큐에 추가할 때, 다음 정점을 방문하지 않았을 때뿐만 아니라 '다음 정점을 동일한 시간이 걸리는 다른 방법으로 방문한 적이 있었을 때'에도 추가해줘야 한다. 이렇게 해야 최단 경로의 모든 경우를 구할 수 있다.

 

# 백준 12851 숨바꼭질2 골드4 https://www.acmicpc.net/problem/12851
# 걷기: x-1 or x+1
# 순간이동: 2*x
from collections import deque
n, k = map(int, input().split())
visited = [0] * (100000+1)

def bfs(start):
    ans_cnt = 100001 # 최단시간 저장
    path_num = 0 # 최단 경로의 수 저장
    q = deque([(start, 0)])

    while q:
        x, cnt = q.popleft()

        # 최단경로가 아닌 것은 그냥 넘어간다.
        if cnt > ans_cnt:
            continue
        
        if x == k:
            if ans_cnt == 100001:
                ans_cnt = cnt # 최단시간 업데이트

            if cnt == ans_cnt:
                path_num += 1 # 최단 경로이므로 path_num 업데이트

        for i in [2*x, x-1, x+1]:
            if -1 < i < 100001:
                # 방문하지 않았거나, 동일한 시간이 걸리는 다른 방법으로 방문한 적이 있었을 때:
                if not visited[i] or visited[i] == cnt + 1:
                    visited[i] = cnt + 1
                    q.append((i, cnt+1))
    return ans_cnt, path_num

ans_cnt, path_num = bfs(n)
print(ans_cnt)
print(path_num)

 

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