[BOJ] 13913. 숨바꼭질 4

문제

숨바꼭질 4 (https://www.acmicpc.net/problem/13913)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 이전 12851. 숨바꼭질 3 문제에서 방법에 약간 변형을 준 것이다.
  • 이제는 경로를 출력해야하는데, DFS야 쉽게 탐색 경로를 출력할 수 있다지만, BFS 에서는 어떻게 해야할까?
    • 현재 위치 cur 에 오기 직전 위치를 담는 리스트(path_list)를 만들자.
      예를 들어, 현재 위치가 3이고, 다음으로 이동할 위치가 2, 4, 6이면,
      path_list[2], path_list[4], path_list[6] = 3 이 된다.
      물론 여기에도, 최소 시간으로 왔는지 체크해야 한다.
    • 그리고 최종 위치 k 에 도달했을 때, 이 리스트를 역으로 따라가면, 어떤 위치에서 왔는지 순서대로 출력할 수 있다. (path)
• 코드

import sys
from collections import deque

def get_path(k, n, path_list):
    path, idx = [], k

    while True:
        path.append(idx)
        if idx == n:
            break
        idx = path_list[idx]
    return path[::-1]

def bfs(n, k):
    # 바로 처리할 수 있는 경우
    if n >= k:
        return n-k, list(range(n, k-1, -1))

    # q : bfs queue로, (이전 위치, 현재 위치) 를 담음.
    # visited[j] : j위치에 방문한 최소 step을 담음. 방문전 기본값은 inf.
    # path_list[j] : j에 오기 직전 인덱스를 담음. 방문전 기본값은 -1.
    # path : 반환할 경로를 담음.
    q = deque([(n, n)])
    visited = [float('inf')] * 100001
    visited[n] = 0
    success, path_list, path = False, [-1] * 100001, None

    while q and not success:
        size = len(q)

        for _ in range(size):
            cur_path = q.popleft()
            cur = cur_path[1]

            next_move = [cur-1, cur+1, cur*2]

            # cur : 현재 위치
            # j : 다음으로 이동할 위치
            for j in next_move:
                if j >= 0 and j <= 100000 and visited[cur] + 1 < visited[j]:
                    visited[j] = visited[cur] + 1
                    path_list[j] = cur

                    if j == k:
                        path = get_path(j, n, path_list)
                        success = True

                    q.append((cur, j))

    return visited[k], path

n, k = list(map(int, sys.stdin.readline().split()))
n, path = bfs(n, k)
print(n)
print(*path)