[파이썬, Python] 백준 2644: 촌수계산

문제

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

2644번: 촌수계산

코드

import sys
sys.setrecursionlimit(10**7)

n = int(input())
a, b = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
res = list()

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def dfs(v, cnt):
    cnt += 1
    visited[v] = True
    
    if v == b:
        res.append(cnt)
    
    for i in graph[v]:
        if not visited[i]:
            dfs(i, cnt)

dfs(a, 0)

if len(res) == 0:
    print(-1)
else:
    print(res[0] - 1)

설명

재귀 제한을 늘려주기 위해 'sys.setrecursionlimit'을 사용해 주었다.

이후 주어진 입력값을 받아주고,
dfs를 위한 그래프와 방문 리스트를 생성해 준다.
정답값을 넣기 위한 리스트도 하나 만들어준다.

이후 일반적인 dfs와 동일하게 진행해 준다.

우선 노드의 연결 관계를 입력받아준다.
그리고 dfs에 cnt 값을 넣어주어 몇 번 진행되었는지(촌수가 어떻게 되는지)를 파악한다.
dfs가 시작할 때 cnt를 1 늘려주고,
이때 dfs를 진행하는 노드의 번호가 목표 노드의 번호와 같으면 현재의 cnt값을 res에 넣어준다.

그 외의 경우에는 dfs를 계속 진행한다.

dfs를 종료하고 결괏값이 존재하면 결괏값의 1을 뺀 값(dfs 시작 부분에 1을 늘렸으므로)을 출력.
그렇지 않으면 -1을 출력한다.