[백준|파이썬] 2644: 촌수계산 (실버2)

문제

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

2644번: 촌수계산

 

 

🐍파이썬

import sys

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
chon = [[] for _ in range(n+1)]
for _ in range(1, m+1):
    c, d = map(int, sys.stdin.readline().split())
    chon[c].append(d)
    chon[d].append(c)
visited = [-1 for _ in range(n+1)]	#친척관계가 없는 경우 -1을 출력하기 위해 -1로 초기화
visited[a] = 0	#시작

#DFS
def dfs(start):
    for i in chon[start]:	#시작노드와 연결된 모든 노드에 대해
        if visited[i] == -1:	#방문한 적 없는 노드인 경우
            visited[i] = visited[start] + 1	#촌수+1
            dfs(i)	#깊이우선탐색

#BFS
def bfs(start):
    queue = []
    queue.append(start)	#시작노드 삽입
    while queue:	#큐가 빌때까지 반복
        v = queue.pop(0)	#큐의 가장 처음 노드를 꺼내기
        for i in chon[v]:	#해당 노드와 연결된 모든 노드에 대해
            if visited[i] == -1:	#방문한 적 없는 노드인 경우
                visited[i] = visited[v] + 1	#촌수+1
                queue.append(i)	#큐에 노드를 추가

dfs(a)
# bfs(a)
print(visited[b])	#end 노드의 값을 프린트해 촌수를 출력