[백준] 13549번 숨바꼭질 3 #Python #BFS

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

13549번: 숨바꼭질 3

 

👉  문제 접근

n = 5,  k = 17

 

n에서 k까지 도달할 수 있는 최소시간을 구해야하므로

근거리부터 가능한 모든 경우를 본다. (분홍색 -> 노란색 -> 보라색). 즉, BFS

 

dist[i] : n으로부터 i까지의 거리

visited[] : 큐에 넣으면 방문처리 -> 중복을 피할 수 있다.

 

목표한 숫자 k를 만나면 탐색을 멈추고 dist[k]를 출력한다.

 

 

✍️ 큐를 이용해 주변노드부터 탐색하는 BFS의 동작과정

 

 

✍️ 5부터 17까지의 최단거리를 찾고 난 뒤 dist[] 의 내용

 

✍️ 정답 

from collections import deque

n, k = map(int, input().split())

max = 100001

dist = [0]*max
visited = [False]*max

queue = deque()
queue.append(n)
visited[n] = True

def dfs():

    while queue:
        x = queue.popleft()
        if x == k:
            return

        if 0 <= 2 * x < max and not visited[2 * x]:
            t = 2 * x
            dist[t] = dist[x]
            visited[t] = True
            queue.append(t)

        if 0 <= x - 1 < max and not visited[x - 1]:
            t = x - 1
            dist[t] = dist[x] + 1
            visited[t] = True
            queue.append(t)

        if 0 <= (x + 1) < max and not visited[x + 1]:
            t = x + 1
            dist[t] = dist[x] + 1
            visited[t] = True
            queue.append(t)

dfs()

print(dist[k])
# for i in range(1, k+1):
#     print(i, '까지의 길이 : ', dist[i])
# print()