[백준/Python] 1697번: 숨바꼭질 (BFS활용)

📖  문제 링크

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

1697번: 숨바꼭질

 

👩‍💻  문제풀이

 

처음엔 DP문제라고 생각하고 풀었는데, 가뜩이나 잘 못하는 DP인 데다 정답도 나오지 않았다. 

찾아보니 BFS 활용문제.... BFS는 더 못해서 산 넘어 산^^..

각종 블로그를 통해 정답코드를 분석해봐도 너무나도 방대한 양으로 진행되어 파악 불가......

 

 

그래서 BFS 기본코드를 디버깅하면서 돌아가는 모습을 확인했다. 

#  bfs 기본 코드 

def bfs(graph, start_node):
    visit = list()
    queue = list()
    
    queue.append(start_node)
    
    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
            
    return visit

 

만약 위와 같은 트리로 기본 코드를 돌린다면,

 

1) 1번 노드가 큐에 들어감 (현재 큐: 1) 

2) 큐의 제일 앞에 위치한 노드를 꺼낸다. (현재 큐의 맨 앞 노드는 1이므로 1을 꺼냄)

3) 노드에 연결된 자식 노드들을 큐의 맨뒤에 차례로 붙여준다. (현재 큐 : 2, 3)

4) 큐의 맨앞 노드를 꺼낸다(2번을 그대로 하는 것. 현재 큐의 맨 앞 노드는 2이므로 2를 꺼낸다.)
5) 2번 노드를 꺼냈으므로, 2번 노드에 연결된 자식 노드들을 큐의 맨 뒤에 차례로 붙인다(3번 반복, 현재 큐 : 3, 4, 5, 6 )

6) 2~3번을 반복 

 

이렇게 하면 순회 순서는 (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9)가 된다. 

 

 

이렇게 기본 코드의 동작 방식을 익히고 나서 본 문제를 다시 보았다. 

처음 출발지(x)부터 x-1, x+1, x*2 의 세 가지 방식으로 나아갈 수 있고, 

각각의 방식 또한 -1, +1, *2로 계속 뻗어나간다. 

 

 

그렇기에 기본 BFS 코드에서 각각의 계산된 경우를 조회하도록 코드를 추가하고, 

목적지와 노드가 같아지면 코드를 중단한다. 예제로 보았을 때 특정 노드가 17이 되면 종료한다는 의미이다. 

 

 

그리고 중요한 점은 파이썬에서 queue가 아닌 deque를 써야 한다는 점! 

queue는 시간초과의 원인이 된다. 

 

 

다음에 이 문제를 다시 풀 땐 어려움 없이 풀 수 있길... 

 

 

✅  최종 코드

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

visit = [0] * 1000001

def bfs(n):
    queue = deque()
    queue.append(n)
    while queue:
        node = queue.popleft()
        if node==k:
            print(visit[node])
            return
        for next in (node-1,node+1,node*2):
            if 0<=next<100001 and not visit[next]:
                visit[next] = visit[node]+1
                queue.append(next)
                
bfs(n)