백준 13549 숨바꼭질 3

🐸 문제 정보

13549번: 숨바꼭질 3

 

🤖 알고리즘

BFS

 

⏱️ 풀이 시간

38.02m

 

📝 풀이

BFS임에도 이렇게 오래 걸린 이유는.. 처음에 백트래킹으로 풀었고 + 순서에 따라 답이 달라지는거에 대해 고려하지 못했다.

생각해보면 단순한 BFS문제 같지만, 거리를 계산할 때 순서가 아래와 같아야한다.

1. *2
   • 시간이 늘어나지 않기 때문에 우선순위가 가장 높음
2. -1
3. +1

1번은 그렇다 쳐도, 2번 3번에 대한 해답은 질문 게시판을 뒤지다가 알아냈다!

 

글 읽기 - x + 1, x - 1 순서에 따라서 답이 달라지는 이유가 뭔가요?

 

🧑‍💻 나의 답

# pypy3

import sys
from collections import deque
input = sys.stdin.readline
INF = sys.maxsize
MAX = (10 ** 5) + 1

n, k = list(map(int, input().rstrip().split()))
visited = [False] * MAX
log = [INF] * MAX

q = deque([n])
log[n] = 0
while q:
    s = q.popleft()
    if s == k:
        break
    for ns, nl in [(2 * s, log[s]), (s - 1, log[s] + 1), (s + 1, log[s] + 1)]:
        if (0 <= ns < MAX) and (not visited[ns]) and (nl < log[ns]):
            log[ns] = nl
            visited[ns] = True
            q.append(ns)

print(log[k])