13913 숨바꼭질4 백준 파이썬

문제)

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

13913번: 숨바꼭질 4

 

소스코드)

from collections import deque
n, k = map(int, input().split())
visited = [-1] * 100001
move = [0] * 100001

def path(x, k):
    ans= []
    temp = x
    for _ in range(visited[k]+1):
        ans.append(temp)
        temp = move[temp]
    return ans[::-1]

def bfs(n, k):
    q = deque()
    q.append(n)
    visited[n] = 0
    while q:
        temp = q.popleft()
        if temp == k:
            print(visited[temp])
            a = path(temp, k)
            print(*a)
            break
        n1 = temp + 1
        n2 = temp - 1
        n3 = temp * 2

        for m in [n1, n2, n3]:
            if 0 <= m <= 100000 and visited[m] == -1:
                visited[m] = visited[temp] + 1
                q.append(m)
                move[m] = temp

bfs(n, k)
#print(visited)

 

정답의 조건중 수빈이가 동생을 찾는 빠른 시간은 쉽게 해결했으나 어떻게 이동했는 지를 어떻게 접근해야할 지 몰라 헤맸었다.

다른 사이트의 코드를 참고해 공부하니

move 변수에 인덱스에는 자식노드에 해당하고 값에는 부모노드를 입력하는 것이다.

와우!!! 대단한 발상이라 기억하고자 글도 쓰게됐다.

bfs를 다 돌려서 찾았을 때 path함수를 호출해 move[k]에 적힌 부모노드를 찾아서 거꾸로 올라가는 것이다.

이 부분 발상이 안되서 dfs로 다시풀어야하나 고민했는데 이런 방법도 있었다.