[2644] 촌수 계산하기 in python



dfs, bfs 두 방식 모두 풀 수 있었던 문제!

 

처음엔 dfs를 총 2번 돌려서

촌수를 더하는 방식으로 계산하려고 했으나

너무 비효율적인 것 같아서 패쓰..

 

 

이 촌수 그래프는

무방향 그래프이니까

array[자식]=부모

array[부모]=자식

이런식으로 양쪽의 값을 각각 넣어줘야한다.

 

 

import sys
sys.setrecursionlimit(300000)
n=int(input())
yeon,kim=map(int,input().split())
m=int(input())
array=[[] for _ in range(n+1)]
visited=[0 for _ in range(n+1)]

for _ in range(m):
    p,c=map(int,input().split())
    array[p].append(c)
    array[c].append(p)
    #무방향 그래프니까 둘다 넣어줌

def dfs(node):
    for i in array[node]:
        if not visited[i]:
            visited[i]=visited[node]+1
            dfs(i)
dfs(yeon)
print(visited[kim] if visited[kim]>0 else -1)