[boj] 백준 13549 숨바꼭질 3 python 풀이(bfs)

감자156 2023. 7. 29. 13:00

문제

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

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

문제 풀이

cost가 작은 순간이동을 우선으로 하여 bfs 돌림

코드

import sys
input = sys.stdin.readline
import collections

N, K = map(int,input().split())

q = collections.deque()
q.append((N,0))
visited = [0 for _ in range(100001)]
visited[N] = 1

while q:
    cur_loc, time = q.popleft()
    if cur_loc == K:
        break

    for i in range(3):
        if i == 0:
            n_loc = cur_loc * 2
            n_time = time
        elif i == 1:
            n_loc = cur_loc -1
            n_time = time + 1
        else:
            n_loc = cur_loc+1
            n_time = time + 1

        if 0<=n_loc<=100000 and visited[n_loc] == 0:
            q.append((n_loc, n_time))
            visited[n_loc] = 1
            
print(time)