[백준/파이썬] 13549번

📍백준 13549번 문제

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

코드

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


start, end = map(int, input().split())
graph = [-1 for _ in range(100001)]
graph[start] = 0
queue = deque()
queue.append(start)

while queue:
    target = queue.popleft()
    if target == end:
        print(graph[target])
        break
    a, b, c = target-1, target+1, target*2
    if 0 <= a < 100001 and graph[a] == -1:
        graph[a] = graph[target] + 1
        queue.append(a)
    if 0 <= c < 100001 and graph[c] == -1:
        graph[c] = graph[target]
        queue.appendleft(c)
    if 0 <= b < 100001 and graph[b] == -1:
        graph[b] = graph[target] + 1
        queue.append(b)

풀이

BFS를 이용해서 풀면 된다.

• 최단 시간을 구해야 하므로 이동시간이 0초인 2x가 가장 우선순위가 높다.2x는 appendleft하여 바로 queue돌릴 수 있도록 한다.
• 나머지 값은 append()하여 큐에 더해주면 된다.
• c가 b보다 앞에 있는 이유는 x*2 == x+1인 경우가 있기 때문에 우선순위가 높은 c값을 먼저 처리해야 한다.