[DFS, BFS] 백준 1697번: 숨바꼭질

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

1697번: 숨바꼭질

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

www.acmicpc.net

import collections
n, k = map(int, input().split())

q = collections.deque()
q.append(n)

discovered = [n]
count = 0
while q:
    for i in range(len(q)):
        cur = q.popleft()
        if cur == k:
            print(count)
            quit()

        next = [cur-1, cur+1, 2*cur]
        for j in range(3):
            if next[j] not in discovered and 100000>=next[j]>=0:
                discovered.append(next[j])
                q.append(next[j])
    count += 1

처음엔 뭔 문제지? 했는데 bfs로 풀 수 있다.

tree의 가지가 무한히 뻗어나가지 않게 적절히 가지치기를 해주면 된다. (discovered)

근데 한가지 걸렸던 건 나는 이 유형이 그래프 문제임을 알고 들어갔지만

만약 유형을 몰랐어도 내가 bfs 접근을 생각할 수 있었을 까란 생각이 들었다..