[백준 - Python] 2644. 촌수 계산 (DFS/BFS)

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

2644번: 촌수계산

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)

a, b = map(int, input().split())
m = int(input())
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

result = -1
cnt = 0
def dfs(v, cnt):
    global result
    visited[v] = True
    if v == b:
        result = cnt
    cnt += 1
    for i in graph[v]:
        if not visited[i]:
            dfs(i, cnt)

dfs(a, cnt)

print(result)

 

문제를 읽고 난 후,

입력으로 주어지는 촌수를 계산해야 하는 두 사람의 번호 중 하나를 시작으로 dfs 탐색을 하여

다른 사람에 도달할 때까지 카운팅을 세어주고

도달하지 못하면 그래프로 연결되어 있지 않으므로 -1을 출력하도록 하면 되겠다고 생각했다.

 

아이디어 자체가 어려운 문제는 아니었다.