백준: 13913 숨바꼭질 4

숨바꼭질 시리즈

• 숨바꼭질
• 숨바꼭질 2
• 숨바꼭질 3
• 숨바꼭질 4

 

문제

13913번: 숨바꼭질 4

 

문제 풀이

 1697 숨바꼭질 문제에서 찾을 수 있는 경로를 출력하는 문제이다. 몇 초 만에 찾을 수 있는지 기록하는 것처럼 2차원 배열을 통해, 방문 경로를 기록해두면 쉽게 해결 할 수 있다. 예시에서는 그림과 같이 하나의 문제에 대해 2가지 경로를 출력하였지만 하나의 경로만 정상적으로 출력하여도 답으로 처리 되는 것 같다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        cur_loc = q.popleft()
        if cur_loc == k:
            return visited[cur_loc][TIME]

        for next_loc in (cur_loc - 1, cur_loc + 1, cur_loc * 2):
            if 0 <= next_loc < MAX_LOC and not visited[next_loc][TIME]:
                visited[next_loc][TIME] = visited[cur_loc][TIME] + 1
                visited[next_loc][PATH] = cur_loc
                q.append(next_loc)


if __name__ == '__main__':
    MAX_LOC, TIME, PATH = 100001, 0, 1
    n, k = map(int, stdin.readline().split())
    visited = [[0, 0] for _ in range(MAX_LOC)]
    print(bfs(n))

    answer = [k]
    while k != n:
        k = visited[k][PATH]
        answer.append(k)

    print(*answer[::-1])