[백준/파이썬] 12851번

📍백준 12851번 문제

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

코드

import sys
from collections import deque
input = sys.stdin.readline


start, end = map(int, input().split())

visited = [0] * (100001)
que = deque()
que.append(start)
visited[start] = 0
cnt = 0

while que:
    cur = que.popleft()
    if cur == end:
        time = visited[cur]
        cnt += 1
        continue
    for i in [cur+1, cur-1, cur*2]:
        if 0 <= i < 100001 and (visited[i] == 0 or visited[i] == visited[cur]+1):
            que.append(i)
            visited[i] = visited[cur] + 1

print(time)
print(cnt)

풀이

최단 경로의 개수를 구해야 하므로 현재 위치와 마지막 위치가 같을때, break하면 안된다. cnt에 값을 추가해주고 continue로 다른 방법이 있는지 모색해본다.