[백준 13913번] 파이썬 - 숨바꼭질 4

백준 13913_숨바꼭질4

시간 제한 2초, 메모리 제한 512MB

# 조건

• 수빈이는 동생과 숨바꼭질을 하고 있다.
• 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
• 수빈이는 걷거나 순간이동을 할 수 있다.
  • 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
  • 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.
• N과 K는 정수이다.

출력

• 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
• 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

# 접근 방법

• BFS를 이용하여 풀어준다.
• for 반복문의 범위로 x-1, x+1, x * 2를 넣어주며 현재 위치에서 이동시키고 route에 추가해준다.
• 또한, 시작 위치가 도착 위치보다 큰 경우는 -1씩 가는 방법 밖에 없으므로 bfs를 시작하기 전에 비교해주면 시간 초과를 해결할 수 있다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import deque

def bfs(s, e):
    visited = [0] * 100001
    q = deque()
    q.append([s, [s]])
    visited[s] = 1
    while q:
        si, route = q.popleft()
        if si == e:
            return route
        for i in [si*2, si-1, si+1]:
            if i < 0 or i >= 100001:
                continue
            if visited[i] != 0:
                continue

            visited[i] = 1
            q.append([i, route + [i]])

st, en = map(int, input().split())
if st > en:
    print(st-en)
    print(*list(i for i in range(st, en-1, -1)))
else:
    result = bfs(st, en)
    print(len(result)-1)
    print(*result)