(Python/🥇2)백준알고리즘 12851번: 숨바꼭질2

문제 바로가기 

숨바꼭질 2

 

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력:

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

 

출력:

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

 

풀이:

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n,k = map(int,input().split())
dp = [-1] * 20
dp[n] = 0
Q = deque()
Q.append(n)
# 제일 빠르게 가는 방법
count = 0
while Q:
    x = Q.popleft()
    if x == k :
        count += 1
    for next_node in [(x-1),(x+1),(2*x)]:
        if 0 <= next_node < 20:
            # 방문 아직 안 했거나, 이미 방문 했지만 현재길이 +1 인 경우
            if dp[next_node] == -1 or dp[next_node] == dp[x] + 1:
                dp[next_node] = dp[x] + 1
                Q.append(next_node)
print(dp)
print(count)

 

bfs + dp 문제 이다

기본적인 bfs 문제인데 거기에 최단거리로 올 수 있는 방법의 수를 구하는게 문제이다. 

방문을 했을때 방문처리로 해버리면 1개 밖에 못 구한다. 

그것을 방지하기 위해서 dp[next_node] = dp[x] + 1 인데

 

예를들어 dp[10] 에 3번 만에 방문한적 있는경우 dp[9] 에 방문하는데 2번만에 방문했다고 치면 dp[10] 방문하는데 3 이다.

그러면 최단거리로 가는 방법이 맞기 때문에 next_node 를 넘겨준다.