[백준] 13549번 숨바꼭질 3 (python, bfs)

728x90
반응형

www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

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

www.acmicpc.net

2보다는 쉽다

더 짧게 갈 수 있는 경우 (check)를 더 작게 업데이트 해주자 

from collections import deque

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

q = deque()
q.append(N)

check=[-1]* MAX_SIZE
check[N]=0
while q:
    x = q.popleft()
    if x==K:
        print(check[x])
        exit()
    for y in [x + 1, x - 1]:
        if 0 <= y < MAX_SIZE:
            if check[y]==-1 or check[y]>check[x]+1:
                check[y]=check[x]+1
                q.append(y)
    if 0<=x*2<MAX_SIZE:
        if check[x*2]==-1 or check[x*2]>check[x]:
            check[x*2]=check[x]
            q.append(x*2)
728x90
반응형

'백준' 카테고리의 다른 글

[백준] 14226번 이모티콘 (bfs, 파이썬)  (0) 2020.10.16
[백준] 13913번 숨바꼭질4  (0) 2020.10.16
[백준] 12851번 숨바꼭질 2 (bfs, 파이썬)  (1) 2020.10.16
[백준] 2178번 미로탐색 (bfs, python)  (0) 2020.10.14
[백준] 1516번 게임개발 (파이썬, 위상정렬, 골드3)  (0) 2020.10.10
TAGS.

Comments