코드

from collections import deque

n, k = map(int, input().split())
max_range = 100001
visited = [0 for _ in range(max_range)]

# seq[i] = i에 도착하기 전의 좌표. 즉, i 전에 출발한 좌표를 저장할 리스트
seq = [0 for _ in range(max_range)]

# 이동 경로를 만들어주는 메소드
def sequence(k):
    # 이동 경로를 담을 리스트
    path = []
    
    # 이동할 때 마다 도착한 좌표를 업데이트 해줄 임시 변수
    temp = k # 마지막 도착 경로는 k
    
    # 1~visited[k]까지 반복 => 움직인 횟수와 동일하게 반복 == 경로의 개수
    for _ in range(1, visited[k]+1):
        
        # 이동 경로를 path에 저장
        path.append(temp)
        
        # seq[temp] => temp에 도착하기 전에 있던 직전의 좌표가 됨
        # 이 좌표를 다시 temp에 넣어줌
        # 이 과정을 for문으로 반복하면 지나온 경로를 되감기 하듯이 거슬러 올라갈 수 있음
        temp = seq[temp]
        
    # 경로를 역순으로 출력
    print(' '.join(map(str, path[::-1])))

def bfs(n):
    q = deque()
    q.append(n)
    
    visited[n] = 1
    
    while q:
        x = q.popleft()
        
        # 동생을 찾았을 때
        if x == k:
            print(visited[k]-1) # 소요 시간 출력
            sequence(k)
            return
        
        for nx in (x-1, x+1, x*2):
            if nx < 0 or nx >= max_range:
                continue
                
            if visited[nx] == 0:
                visited[nx] = visited[x] + 1
                seq[nx] = x # nx에 도착했을 때, 도착하기 전의 좌표 x를 seq에 저장
                q.append(nx)
        
bfs(n)

문제 해설

숨바꼭질의 변형 문제.

이번엔 동생을 찾는 최단 시간과 그 경로를 출력하라는 문제이다.

nx 좌표에 도착했을 때, 도착하기 직전의 좌표를 담아줄 별도의 리스트를 생성하여 문제를 해결하였다.

  • seq[nx] = x
    • x : nx에 오기 전에 위치해있던 좌표

visited 테이블이 갱신될 때 마다 위의 리스트에 이전 좌표의 값을 넣어주고 이를 방문한 역순으로 출력해주면 정답으로 인정된다.

댓글남기기

참고