[백준 / 파이썬] 1697번 숨바꼭질

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k:
            print(a[x])
            break
        for i in (x-1, x+1, x*2):
            if 0 <= i <= MAX and not a[i]:
                a[i] = a[x] + 1
                q.append(i)

MAX = 10 ** 5
a = [0] * (MAX + 1)
n, k = map(int, input().split())

bfs()

 

선형구조로서의 자료구조 - Stack, Queue, Deque

Stack은 LIFO - 가장 먼저 넣은 것이 맨 마지막에 나온다

Queue는 FIFO - 가장 먼저 넣은 것이 가장 먼저 나온다

Deque - 양쪽 모두 입출력 가능

 

BFS 방법으로 풀이 가능

MAX는 k를 넘어갈 수 있으니까 넉넉하게 지정

q.append(n)으로 처음 시작점을 deque에 추가

if문으로 수빈이의 위치가 동생 위치 k와 같아지면 a[x] 출력으로 시간 구해주고 종료