BOJ 2644 - 촌수계산

문제

백준 온라인 저지 - 2644번

풀이 과정

문제 조건을 통해 각 자식은 오직 하나의 부모만 주어지므로 사이클 없는 무방향 그래프로 나타낼 수 있습니다.

따라서 촌수를 계산하고 싶은 두 사람중 임의로 한명을 선택한 뒤 다른 한명에 도달하는 거리를 계산하면 답을 구할 수 있습니다.

이때, 도달 가능성 유무는 DFS 를 통해 계산된 거리값을 통해 알 수 있도록 하였습니다.

코드

import sys

n = int(input())
target = list(map(int, sys.stdin.readline().split()))
m = int(input())
adj = [[] for _ in range(n+1)]
for _ in range(m):
    frm, to = list(map(int, sys.stdin.readline().split()))
    adj[frm].append(to)
    adj[to].append(frm)


def dfs(here, cost, visit):
    if here == target[1]:
        return cost

    visit.append(here)

    for near in adj[here]:
        if near not in visit:
            dist = dfs(near, cost+1, visit)
            if dist != -1:
                return dist
    return -1


def solution():
    visit = []
    ans = dfs(target[0], 0, visit)
    return ans


print(solution())