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

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

 

# 풀이과정 (BFS 이용)

1. 수빈이가 이동하는 방법은 앞으로 한칸, 뒤로 한칸, 현재 칸의 두배 위치로 점프, 이렇게 3가지이다.
2. 각 위치에 도달하기 위한 최소 시간을 나타내는 리스트를 하나 설정
3. 최단 시간을 구해야 하기에, 현재까지의 최소시간을 의미하는 전역변수 maxCnt를 설정함
4. 최단 기록의 경우의 수를 나타내는 변수 num을 설정함
5. BFS를 이용하여 큐에 수빈이가 동생을 잡기위해서 현재까지 소요된 시간 및 현재위치를 넣음
6. 이것을 반복하여 동생의 위치에 도달하게 되면, 그때를 기준으로 소요된 시간이 총 걸린 시간임
7. maxCnt보다 현재 소요된 시간이 크다면, 해당 경우의수는 더이상 계산하지 않음
8. 각 위치별로 도달에 필요한 최소 시간을 나타내는 리스트를 하나 설정
9. 만약 큐에서 뽑은 위치와 시간이 리스트에 기록된 시간보다 크다면 해당 경우의수는 더이상 계산하지 않음
10. 이를 반복하며, maxCnt가 업데이트되면 num을 1로 초기화
11. 만약 걸린 시간이 maxCnt와 같다면 num값을 1증가시킴
12. 큐에 더이상 데이터가 없으면 결과를 출력하고 끝냄

# 기존에 위치별 소요시간을 나타내는 리스트의 크기를 동생이 있을 수 있는 최대 위치인 100000으로 잡았더니 틀렸다.

이는 수빈이가 100000을 넘는 위치까지 갔다가 돌아오는 경우의 수가 있기 때문이므로, 위치별 소요시간을 나타내는 리스트의 크기를 크게 300000으로 잡았다.

 

 

[BFS를 이용한 코드 - 성공]

# ex_12851

import sys
from collections import deque
N,K = map(int,sys.stdin.readline().split())
timeTable = [1e9 for _ in range(300001)]
maxCnt = 1e9
num = 0
q = deque([])
q.append((N,0))

def bfs():
    global maxCnt, num
    while q:
        start,cnt=q.popleft()
        if start > 300000:
            continue
        if cnt > maxCnt or cnt > timeTable[start]:
            continue
        timeTable[start] = cnt
        if start==K:
            if cnt==maxCnt:
                num+=1
            else:
                maxCnt=cnt
                num=1
            continue
        q.append((start*2,cnt+1))
        q.append((start+1,cnt+1))
        q.append((start-1,cnt+1))

bfs()
print(maxCnt)
print(num)