Problem Solving/DFS, BFS
[DFS, BFS] 백준 1697번: 숨바꼭질
ggyongi
2021. 5. 29. 16:13
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 접근을 생각할 수 있었을 까란 생각이 들었다..