[백준] 13913번: 숨바꼭질 4 - python

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

 

시험과 플젝 끝난 후 간만에 알고리즘 풀이

 

BFS이므로 ch 리스트를 체크하는 용도 말고 dis를 넣어서 체크해도 문제가 되지 않는다.

그 후 여기선 최단으로 바뀌는 경로의 값을 전부 다 넣어서 출력해줘야되기에 dis안에 전에 now를 넣어서 저장시켜준다.

그 후 만약 n == k 가 되면 dis를 돌아서 answer안에 투입 후 출력해준다. 

from collections import deque
n, k = map(int, input().split())

ch = [0] * (100001)
dis = [0] * (100001)

ch[n] = 0
dis[n] = 0

dq = deque([n])
while dq:
    now = dq.popleft()
    if now == k:
        print(ch[now])
        answer = []
        while now!=n:
            answer.append(now)
            now = dis[now]
        answer.append(now)
        answer.reverse()
        print(*answer)
        exit()

    for next in(now-1, now+1, now*2):
        if 0<=next<100001:
            if ch[next] == 0:
                ch[next] = ch[now] + 1
                dis[next] = now
                dq.append(next)

 

완성