백준 12815번 숨바꼭질2 with python

문제

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

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

 

풀이

이 문제는 맨 처음 문제를 보고는 dfs를 이용하여 재귀적으로 n+1,n-1,2*n의 경우를 모두 따져보면 되지 않을까라고 생각했지만 이는 시간 초과를 유발하게 된다. 따라서 bfs를 풀되 효율적으로 코드를 개선해야 한다. 이 문제에서는 최소의 조건이라는 타이틀을 걸었기 때문에  n+1,n-1,2*n이 한 번씩 일어날 때마다 시간을 1씩 증가시켜주며, 가장 빠른 시간으로 찾을 떄 1번 이상 방문했을 경우는 방법의 개수를 더해준다

 

from collections import deque
# 숨바꼭질 bfs 이용
N,K=map(int,input().split()) # 수빈이, 동생
ch=[[-1,0] for _ in range(100001)]

# 수빈이가 동생을 찾는 가장 빠른 시간
# 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수

def bfs(n):
    de=deque()
    de.append(n)
    ch[n][0]=0 # 가장 빠른 시간
    ch[n][1]=1 # 방법의 수

    while de:
        x=de.popleft()

        for i in (x+1,x-1,x*2): # 최소의 조건이 되려면 세 가지 경우의 수 중 하나를 고른다
            if 0<=i<100001: 
                if ch[i][0]==-1: #처음 들르는 경우
                    ch[i][0]=ch[x][0]+1 # 시간을 1 증가시킨다
                    ch[i][1]=ch[x][1] # 방법의 개수
                    de.append(i)
                elif ch[i][0]==ch[x][0]+1: # 한번 이상 들르는 경우
                    ch[i][1]+=ch[x][1] # 방법 더하기

ch=[[-1,0] for _ in range(100001)]
bfs(N)
print(ch[K][0])
print(ch[K][1])
                    

K(0 ≤ K ≤ 100,000)의 조건만큼 반복문이 돌아가며, 가장 중요한 부분은 한번 이상 들르는 경우 여태까지 쌓아왔던 방법들을 모두 더해주는 것이다.