[백준] 13913 파이썬(python) : 숨바꼭질 4

13913번: 숨바꼭질 4

 

 

from collections import deque
n, k = map(int, input().split())
visit = [0] *100001
move = [0] *100001
def path(x):
    arr = []
    temp = x
    for _ in range(visit[x]+1): #4
        arr.append(temp) #5
        temp = move[temp] #6
    print(*arr[::-1]) #7
def bfs():
    q = deque([n])
    while q:
        x = q.popleft()
        if x == k:
            print(visit[x]) #2
            path(x) #3
            return
        for nx in (x-1, x+1, 2*x):
            if 0 <= nx < 100001:
                if not visit[nx]:
                    q.append(nx)
                    visit[nx] = visit[x] + 1
                    move[nx] = x #1
bfs()

 

#1 : 자신의 부모노드 저장 => move[현재노드] = 부모노드

#2 : x == k까지 도달해서 방문횟수(=가중치총합) 출력

#3 : path(x) 실행

#4 : visit[x]이 최소시간이자 최소시간으로 방문한 노드들의 개수일테니 range(visit[x]+1)로 지정

#5 : 가장 마지막 방문지부터 하나씩 리스트에 삽입

#6 : move는 자신의 부모노를 값으로 사용하니 반복이 돌때마다 부모노드를 temp로 저장

#7 : 리스트를 역순으로 뒤집고 출력

 

숫자 10001인데 10001로 해서 틀린 원인을 찾느라 너무 오랫동안 고민한 문제였다. 이유를 알았을때의 허탈감이란...

#1같이 부모노드를 값으로 저장하는 방법은 알고 있었지만 그것을 어떻게 꺼내서 출력하는지를 배울 수 있었다. temp변수를 만들어서 방문횟수만큼 반복해서 새로운 리스트에 넣고 역으로 출력한다는 생각은 정말 참신하다.