BFS(너비 우선 탐색): 백준 1697 숨바꼭질

문제: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

풀이:

이 문제의 조건에 보면 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하라고 적혀있다.

그리고 각 이동마다 걸리는 시간이 1초로 간선의 길이가 같다. -> BFS를 사용해 풀면 된다.

 

dist 배열에 각 위치로 이동하는데 걸린 최소 시간을 저장한다. 방문한 위치는 다시 방문하지 않기 때문에 가장 빨리 도착한 시간이 dist 배열에 저장된다.  

 

정답:

import sys
from collections import deque
input = sys.stdin.readline()


def bfs():
    queue = deque()
    queue.append(n)     # queue = ([5])

    while queue:
        x = queue.popleft()
        if x == k:
            print(dist[x])
            break

        for nx in (x-1, x+1, x*2):     # nx = 4, 6, 10
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[x] + 1
                queue.append(nx)


MAX = 100000
n, k = map(int, input.split())
dist = [0] * 100001  # 이동한 횟수를 저장하는 변수

bfs()

 

# 방문체크와 최단거리를 기록하는 리스트를 분리한 코드
def bfs():
    visited[n] = True
    dist[n] = 0
    queue = deque()
    queue.append(n)

    while queue:
        x = queue.popleft()
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and visited[nx] == False:
                visited[nx] = True
                dist[nx] = dist[x] + 1
                queue.append(nx)


n, k = map(int, input.split())
MAX = 100001
visited = [False] * (MAX + 1)
dist = [-1] * (MAX + 1)
bfs()
print(dist[k])