[백준] 13913번: 숨바꼭질4 / Python / 너비우선탐색(BFS)

숨바꼭질4

• 문제
  수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

  수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
  

• 입력
  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

• 출력
  첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

풀이 방법

• 방문 여부 체크를 위한 visited 딕셔너리에 현재 도달한 위치와 소요된 시간을 key, value로 저장하고 갱신한다. 굳이 딕셔너리를 쓰지 않아도 리스트에 visited[moved]=cnt로 저장하면 같은 시간복잡도로 구현할 수 있다.
• 최소 시간으로 이동한 경로를 구해야 하는 것이 이 문제의 핵심인 것 같다. parent[moved] = now 형태로 현재 위치의 이전 위치(부모 노드라고 생각하면 편하다)를 저장해두고, 탐색이 끝났을 때 역추적하면 된다.

from collections import deque

N, K = map(int, input().split())

visited = {N:0} # 현재 위치와 소요 시간(초)을 key, value로 저장
parent = [0] * 100001 # 경로를 역추적 하기 위해 현재 위치(인덱스)의 이전 위치를 저장
q = deque([N])
cnt = 0

def get_path(moved):
    path = []
    tmp = moved
    for i in range(visited[tmp] + 1): # 출발 위치 ~ 도착 위치(K)까지 
        path.append(str(tmp))
        tmp = parent[tmp]
    return " ".join(path[::-1])

def bfs():
    while q:
        now = q.popleft()
        cnt = visited[now]
        
        if now == K:
            print(cnt)
            print(get_path(now))
            return 
        
        cnt += 1
        for moved in [now - 1, now + 1, now * 2]:
            if 0 <= moved <= 100000:
                if visited.get(moved, 0) == 0:
                    visited[moved] = cnt 
                    parent[moved] = now # 경로 추적을 위한 저장
                    q.append(moved)
                    
                
bfs()