[백준 13913] 숨바꼭질 4

1. 문제

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

2. 접근 방법

경로를 어떻게 담냐가 관건이었다.

 

처음에 ㅋㅋㅋㅋ

아무 생각없이 그냥 2차 행렬 만들어서 다 집어넣었다가

메모리 초과 바로 나버리고

 

그 전 인덱스만 담았다.

 

그렇게 해서 최종 인덱스에 도달했을 때,

하나씩 pop 해서 프린트했다.

 

3. 코드

python

from collections import deque

def bfs(n):
    global visited, path
    q = deque()
    q.append(n)
    visited[n] = 0
    while q:
        x = q.popleft()
        if x == K:
            print(visited[x])
            p = []
            while x != N:
                p.append(x)
                x = path[x]
            p.append(n)
            p.reverse()
            print(*p)
            return
        for nx in (x*2, x+1, x-1):
            if 0 <= nx <= MAX and visited[nx] == -1:
                q.append(nx)
                visited[nx] = visited[x] + 1
                path[nx] = x
MAX = 100000
N, K = map(int, input().split())
visited = [-1] * (MAX+1)
path = [0] * (MAX+1)
bfs(N)

4. 마치며

마치며~!