[백준] 12851 - 숨바꼭질2(Python)

문제 출처:

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

아마도 이걸 보시는분들은 다들 문제를 보고오셧기 때문에 따로 문제설명은 안해도 될 것이라 생각합니다.

 

문제 풀이:

숨바꼭질 시리즈 중 하나고 전형적인 BFS 문제입니다.

다만 조금 까다로웠던 점은 최소 시간 뿐 아니라 갈 수 있는 방법의 수를 적어야 한다는 것이다.

처음에는 간단하게 생각했었는데 중복되어서 가는 방법의 수를 세는 것이 어려웠다.

 

from collections import deque

a,b = map(int,input().split())

def bfs(n,k):
    #n: 시작 k: 도착
    #output : time,cnt
    if n==k:
        return 0,1
    if k<n:
        return n-k,1
    #visited[j] : j까지 오는데 최소의 시간 저장
    #ways[j] : j까지 최소 시간으로 오는 방법의 수
    visited = [1e12]*100001
    stack = deque([n])
    ways = [0]*100001
    time=0
    condition = False
    ways[n]=1
    visited[n]=0
    while(stack and not condition):
        size = len(stack)
        for _ in range(size):
            cur = stack.popleft()
            next_move = [cur+1,cur-1,cur*2]
            for j in next_move:
                if(0<=j and j<=100000 and time+1<=visited[j]):
                    ways[j] +=1
                    visited[j] = time+1
                    if j==k:
                        condition=True
                    if not condition:
                        stack.append(j)
        time +=1
    return visited[k],ways[k]

t,cnt = bfs(a,b)
print(t)
print(cnt)

 

ps) 참고로 반례가 아주 잘 되어있는 문제라 공부하기가 좋은 문제였다.

반례 참고 :www.acmicpc.net/board/view/56215