[백준/BOJ] gold4 - 13913번 숨바꼭질4 (Python)

▶13913 - 숨바꼭질4

백준 로고

▶문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

▶입력

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

 

▶출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

728x90

▶풀이

2023.03.12 - [BOJ Code/Gold] - [백준/BOJ] gold5 - 13549번 숨바꼭질 3 (Python)

[백준/BOJ] gold5 - 13549번 숨바꼭질 3 (Python)

이전에 풀었던 문제와 비슷하지만 경로도 알고 있어야 하는 문제이다.

기본적으로 bfs를 이용해서 문제를 푸는 방식은 동일하다.

 

처음에는 queue에 경로도 같이 기록해서 넣어주었다.

그렇게 푸니까 시간초과가 나서 새로운 방식을 사용했다.

 

check라는 새로운 리스트 변수를 생성해 주고, 새로운 곳으로 가게 되었을 때 이전의 위치를 넣어주었다.

예를 들어 5에서 시작해서 다음에 10으로 간다면 check[10]은 5가 되도록 구현했다.

 

그다음에 x가 k가 되었을 때 check를 돌면서 값을 기록하면 된다.

move라는 함수를 만들어서 time만큼 돌면서 값을 li라는 리스트에 넣어주었다.

마지막 리턴할 때 li[::-1]로 해서 reverse 시켜주었다.

 

reverse 시켜주는 이유는 마지막에 도달한 x부터 역으로 시작값을 찾아가기 때문이다.

from collections import deque


def move(x, time, check):
    tmp = x
    li = []
    for _ in range(time + 1):
        li.append(tmp)
        tmp = check[tmp]
    
    return li[::-1]


def bfs():
    queue = deque()
    queue.append((n, 0))
    visit = [0 for _ in range(100001)]
    visit[n] = 1
    check = [0 for _ in range(100001)]

    while queue:
        x, time = queue.popleft()
        if x == k:
            return time, move(x, time, check)
        
        if x + 1 <= 100000 and visit[x + 1] == 0:
            visit[x + 1] = 1
            queue.append((x + 1, time + 1))
            check[x + 1] = x
        
        if x - 1 >= 0 and visit[x - 1] == 0:
            visit[x - 1] = 1
            queue.append((x - 1, time + 1))
            check[x - 1] = x
        
        if x * 2 <= 100000 and visit[x * 2] == 0:
            visit[x * 2] = 1
            queue.append((x * 2, time + 1))
            check[x * 2] = x


n, k = map(int, input().split())

a, b = bfs()
print(a)
print(*b)