백준_python 16953번 A → B (BFS, 그래프 깊이)

<문제 링크>

 

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

 

 

 

<정답 코드>

🔷 sol) bfs를 이용한 목표 값 탐색, 노드 깊이로 연산 횟수 계산

from collections import deque
 
MAX = 10 ** 9
 
def bfs(n):
    q = deque([(n, 1)])     # (노드, 변환 횟수)
    while q:
        v, cnt = q.popleft()
        if v == b:
            return cnt
        for w in [v * 2, (v * 10) + 1]:
            if w <= MAX:
                # cnt + 1 : 자식 노드는 현재 노드보다 깊이 + 1
                q.append((w, cnt + 1))  
    return -1    
 
a, b = map(int, input().split())
print(bfs(a))

 

BFS로 탐색하며 q 맨 앞 요소에 가능한 연산들의 결과값을 추가하면서 목표값 b를 찾는다. 

 

 

그래프 문제를 풀다 보면 특정 노드의 depth를 알아야 하는 경우가 있다.

line 6)  노드 값과 depth를 쌍으로 저장하면 파악하기 쉽다.

line14)  자식 노드를 추가할 때는 현재 노드보다 깊이가 +1되므로 현재 depth+1한 값을 넣어주면 된다. 

 

# 예제 1) bfs내부 q 변화 출력
 
deque([(2, 1)])
deque([(4, 2), (21, 2)])
deque([(21, 2), (8, 3), (41, 3)])
deque([(8, 3), (41, 3), (42, 3), (211, 3)])
deque([(41, 3), (42, 3), (211, 3), (16, 4), (81, 4)])
deque([(42, 3), (211, 3), (16, 4), (81, 4), (82, 4), (411, 4)])
deque([(211, 3), (16, 4), (81, 4), (82, 4), (411, 4), (84, 4), (421, 4)])
.
.
.
 

 

위 코드에 따라 예제 1번을 실행하면, 이와 같이 q에 노드 값과 depth 쌍이 차례로 추가된다.