[백준 Python] 2644번 촌수계산

백준 파이썬 2644번 촌수계산

Silver 2

 

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

 

import sys
input = sys.stdin.readline
from collections import deque
def bfs(a, b):
    q = deque()
    q.append((a, 0))
    q.append((b, 0))
    visited[a], visited[b] = 0, 0
    while q:
        x, dist = q.popleft()
        for i in tree[x]:
            if visited[i] == -1:
                dist += 1
                q.append((i, dist))
                visited[i] += dist+1
            else:
                return visited[i] + dist + 1
    return -1
n = int(input())
tree = [[] for _ in range(n+1)]
visited = [-1]*(n+1)
a, b = map(int, input().split())
m = int(input())
for _ in range(m):
    x, y = map(int, input().split())
    tree[y].append(x)
print(bfs(a,b))

 

1. 트리에 자식 번호에 부모를 넣는다.

2. 공통 부모 노드를 찾아 올라가며, visited[i]에는 누적 거리 값을 넣어준다.

3. 공통 부모 노드를 찾은 경우 누적 거리의 합을 리턴해준다.

4. 공통 부모 노드를 찾지 못 한 경우 -1을 출력해준다.