백준 1697 문제 풀이

3991 단어 문제풀이BFSBFS

🐒 숨바꼭질

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


✍ 나의 풀이

from collections import deque


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

def bfs():
    q = deque()
    q.append(N)
    while q:
        x = q.popleft()
        if x == K:
            print(time[x])
            return
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not time[nx]:
                time[nx] = time[x] + 1
                q.append(nx)

MAX = 10**5 
time = [0] * (MAX +1)

bfs()

🧠 문제 이해

그리디로 푸는건가 싶었는데, 아니고
x-1, x+1, x*2 로 탐색을 뻗어나가면서 값을 찾으면 몇번째 탐색에 찾았는지 출력한다.

좋은 웹페이지 즐겨찾기