[백준] 2644번 촌수계산 파이썬

bled 2021. 6. 10. 20:44

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

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진

www.acmicpc.net

import sys
PeoepleNum = int(sys.stdin.readline())

start_node, end_node = map(int, sys.stdin.readline().split())
N = int(sys.stdin.readline())

graph = dict()

for i in range(1, PeoepleNum + 1):
    graph[i] = []

for j in range(N):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# print(graph)

def bfs(graph, start_node, end_node):
    visited = []
    depth = 0
    need_visit = []
    need_visit.append([start_node, 0])
    while need_visit:
        node, depth = need_visit.pop(0)
        if node == end_node:
            return depth
        if node not in visited:

            visited.append(node)
            
            depth+=1
            for n in graph[node]:
                if n not in visited:
                    need_visit.append([n, depth])


    return -1


print(bfs(graph, start_node, end_node))