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

 

문제링크: https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

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

    n, k = map(int, input().split())    #n는 수빈, k는 동생
    max = 100000                        #n,k <= 100000이기 때문에 최댓값을 잡아줍니다.
    length = [0 for _ in range(max+1)]  #최대값 내의 숫자만큼(100001개) length 배열을 생성
    path = [0 for _ in range(max+1)]    #수빈이가 이 전에 어디를 방문했었는지 알 수 있는 path 생성

    def findpath(x):
        arr = []
        temp = x
        for _ in range(length[x]+1):    #이동을 length[x]번 했다면 length[x]+1개의 수를 출력
            arr.append(temp)
            temp = path[temp]
        revarr = arr[::-1]
        print(*revarr)                  #역으로 프린트 해준다
    def bfs():
        q = deque()                     #queue를 원할때는 효율이 좋은 deque(double-ended queue)를 사용합시다.
        q.append(n)
        while q:                        #q에 체크할 위치가 남아있다면
            temp = q.popleft()

            if temp == k:
                print(length[temp])
                findpath(temp)
                break
            for j in (temp-1, temp+1, temp*2):
                if 0 <= j <= max and not length[j]: 
                	# and문에서 범위 체크 먼저하는게 매우중요해요. 안 그러면 런타임뜹니다.
                    length[j] = length[temp] + 1
                    q.append(j)
                    path[j] = temp

    bfs()

숨바꼭질 문제랑 똑같지만 숨바꼭질 4는 수빈이가 어느 길을 통해서 왔는지도 출력해야해요.
해당 숫자가 그 전에 어디를 방문했는지를 저장해주면 좋겠다고 생각해서 path[]를 만들어서
수빈이가 다음 숫자로 넘어가려고 할 때 "잠깐! 너 어디서 왔었어" 하고 숫자를 기록하면 된다는 느낌으로 저장했습니다 (line 33의 path[j] = temp).

피드백 감사합니다.