백준 2644번: 촌수계산 - 파이썬(DFS)

기본적인 탐색문제로 DFS,BFS알고리즘중 하나를 선택해서 풀면 된다.

나는 DFS를 이용해서 풀었고 DFS알고리즘은 재귀함수를 사용하기 때문에 미리 재귀깊이를 늘려놓는것이 편하다.

 

dfs함수를 만들어주고 check라는 리스트에 계속해서 숫자를 더하는 방법으로 촌수를 계산해보았다.

# 2644번: 촌수계산
import sys
sys.setrecursionlimit(10*5)

def dfs(node):
    for n in graph[node]:
        if check[n] == 0:
            check[n] = check[node]+1
            dfs(n)

n = int(input())
graph = [[] for _ in range(n+1)]
s,e = map(int,input().split())
for _ in range(int(input())):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0] * (n+1)

dfs(s)
print(check[e] if check[e] > 0 else -1)