[백준13913] 숨바꼭질 4

문제

---

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

생각의 흐름

---

수빈이가 X에 있을 때 이동가능한 경우의 수는 X-1, X+1, 2X의 세가지이다. 가능한 경우는 이 세가지이므로 수빈이의 위치를 q에 넣고 이들을 pop하면서 BFS로 탐색을 해주면 된다. 이 때, pop을 했을 때 원소가 K와 같은 값이면 탐색을 종료한다.

방문을 체크하기 위해서는 visit이라는 1차원 리스트를 사용하였다. 리스트에는 이전에 방문한 위치의 값을 넣어주어 탐색을 마친 뒤 거꾸로 찾아가 경로를 출력할 수 있도록 구현하였다.

 

깨달은 점

---

보통 어떤 한 경우에 대해서 가능한 경우의 수가 몇개로 특정되어지는 유형의 문제라면 BFS를 사용하여 모든 가능한 경우를 중복없이 탐색해주면 된다.

 

코드

---

# BOJ 13913

from collections import deque
import sys

N,K = list(map(int, input().split()))
visit = [-1]*100001
if N==K:
    print(0)
    print(N)
    sys.exit()

def bfs():
    while q:
        x = q.popleft()
        if x==K:
            break
        if 0<=x-1<=100000 and visit[x-1]==-1:
            q.append(x-1)
            visit[x-1]=x
        if 0<=x+1<=100000 and visit[x+1]==-1:
            q.append(x+1)
            visit[x+1]=x
        if 0<=2*x<=100000 and visit[2*x]==-1:
            q.append(2*x)
            visit[2*x]=x

visit[N] = -2    #시작지점
q = deque()
q.append(N)
bfs()
i=K
result = []
while visit[i]!=-2:
    result.append(i)
    i=visit[i]
result.reverse()
print(len(result))
ans = [N]+result
print(' '.join(map(str, ans)))