[Algorithm] 백준 BOJ 2644 촌수계산 python 파이썬 그래프 DFS 실버 2

Private 난이도 : ♥♥♡♡♡

2644번: 촌수계산

from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10**6)
n=int(input()) # 전체 사람 수

a,b =map(int,input().split(' ')) # 촌수를 구해야 하는 두 사람
m=int(input()) # 관계 수

graph=defaultdict(list)
for i in range(m):
    x,y= map(int,input().split(' '))# x: 부모, y: 자식
    graph[x].append(y)
    graph[y].append(x)
# print('graph',graph)

def dfs(a,chon,visited):
    childs=graph[a]
    chon+=1
    visited.append(a)
    if b in childs: # 도착
        print(chon)
        exit()
    else:
        for child in childs:
            if child not in visited:
                dfs(child,chon,visited)

visited=[]
dfs(a,0,visited)
print(-1)

설명

• 촌수를 print한 후 프로그램을 끝내버리기 때문에 끝나지 않은 경우는 -1로 해서 코드를 줄일 수 있었다.

배운 점

• dictionary 에 양방향으로 넣는 방법을 처음에 생각하지 못했는데, 넣는 것이 훨씬 나은 것 같다.