[🥇4 / 백준 13913 / 파이썬] 숨바꼭질 4

 

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는 정수이다.

출력

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

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

 

예제 입력 1  5 17	예제 출력 1  4 5 10 9 18 17
예제 입력 2  5 17	예제 출력 2  4 5 4 8 16 17

 

풀이

 

BFS를 통해 최단거리를 찾고, 그 경로를 추적하여 출력하는 문제이다.

 

처음엔 BFS의 Q에 원소를 넣을 때 지나온 경로까지 넣으면 어떨까 생각했다.

잘 작동했지만 36% 부근에서 시간초과에 걸렸다.

 

100000 0 같은 테스트 케이스에서 100000의 최단 경로가 찍히게 되는데,

경로가 들어있는 배열의 수와 크기가 급격하게 커지면서 많은 연산을 요구하게 되는 것이었다.

 

따라서 n > k 일 경우 n-k 를 출력하고 n부터 k까지 for문으로 순회하며 하나씩 출력하는 예외 코드를 작성했다.

결과는 성공이었다.

 

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

n,k = map(int,input().split())
if n>k:
    print(n-k)
    for i in range(n,k-1,-1):
        print(i,end=" ")
    sys.exit()

visit = [False]*100001

q = deque([(n,[n])])
while q:
    pos, path = q.popleft()
    if pos == k:
        print(len(path)-1)
        print(*path)
        break
        
    visit[pos] = True
    
    for i in pos*2,pos+1,pos-1:
        if 100001>i>=0 and not visit[i]:
            q.append((i,path+[i]))
            visit[i] = True

 

하지만 다른 사람들의 코드보다는 느린 편에 속했다.

아무래도 극한의 저격 케이스는 회피했지만 그래도 큐의 배열의 크기와 수가 계속 갱신되며 커지다보니 일어나는 문제인 것 같았다.

 

따라서 다른 방법으로, visit이라는 방문 배열에 True False 만 기록하는 것이 아닌, 그 정점을 찍기 바로 이전의 정점을 기록해두는 방식을 택했다.

이렇게 한다면 큰 연산 없이 쉽게 거슬러 올라가 최단거리를 추적할 수 있다.

 

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

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

# 아래 예외 사항은 딱히 없어도 되지만, 시간 복잡도에 이득이 있다.
if n>k:
    print(n-k)
    for i in range(n,k-1,-1):
        print(i,end=" ")
    sys.exit()

visit = [-1]*100001

q = deque()
q.append(n)
while q:
    pos= q.popleft()
    
    for i in pos*2,pos+1,pos-1:
        if 100001>i>=0 and visit[i]==-1:
            q.append(i)
            visit[i] = pos

# 최단거리 역추적
ans = []
while True:
    ans.append(k)
    if k == n:
        break
    k = visit[k]
print(len(ans)-1)
print(*ans[::-1])