[백준 01697] 숨박꼭질 [Python]

문제

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

 

---

풀이

0 이상 10만 이하의 N과 K에 대해 다음 연산을 통해 N이 K가 되는 가장 빠른 연산 횟수를 구하는 문제다.

BFS를 통해 (연산 결과, 연산 횟수) 쌍을 큐에 담아줬다.

from collections import deque
from sys import stdin

input = stdin.readline

def bfs(start, end):
    queue = deque([(start, 0)])
    visited = [False] * 100_001
    visited[start] = True

요소를 하나씩 제거하며 연산 결과가 K가 될 때 까지 반복했으며,

새로운 N은 0 ~ 100,000을 벗어나지 않고, 계산해본 적 없는 수에 대해서만 다음 탐색 대상으로 선정했다.

    while queue:
        cur, cnt = queue.popleft()
        if cur == end:
            return cnt
        if cur + 1 <= 100_000 and not visited[cur + 1]:
            visited[cur + 1] = True
            queue.append((cur + 1, cnt + 1))
        if cur - 1 >= 0 and not visited[cur - 1]:
            visited[cur - 1] = True
            queue.append((cur - 1, cnt + 1))
        if cur * 2 <= 100_000 and not visited[cur * 2]:
            visited[cur * 2] = True
            queue.append((cur * 2, cnt + 1))

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/01697.py