[백준] 2644 - 촌수계산

문제 링크

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

문제 요약

이 문제는 사람들 간의 촌수를 계산하는 문제입니다. 주어진 사람들 중에서 특정 두 사람 사이의 촌수를 계산하는 프로그램을 작성해야 합니다. 촌수는 부모와 자식 관계를 1촌으로 정의하며, 이를 이용해 두 사람 간의 촌수를 계산합니다.

푼 방법

 

• 주어진 두 사람 간의 촌수를 구하는 문제는 그래프 탐색 문제로 생각할 수 있습니다.
  • 각 사람을 그래프의 노드로 보고, 부모 자식 관계를 간선으로 연결하여 BFS 또는 DFS로 두 노드 간의 최단 경로(촌수)를 계산할 수 있습니다.
  • 저의 경우 재귀적 DFS로 해결했습니다.
• 두 사람이 연결되어 있지 않으면 -1을 출력해야 합니다.

 

정답 코드

def chonsu():  
    result=[]
    def recur(curr, d):
        #print(curr)
        if tree[curr][f2]:
            result.append(d)
            return 
        for x in range(len(tree[curr])):
            if tree[curr][x]:
                tree[curr][x] = False
                tree[x][curr] = False
                recur(x, d+1)
    
    n = int(input())
    f1, f2 = list(map(int ,input().split()))
    m = int(input())

    tree=[[None for _ in range(n+1)] for _ in range(n+1)]

    for i in range(m):
        y, x = list(map(int, input().split()))
        tree[y][x] = True
        tree[x][y] = True
    
    recur(f1, 1)
    if len(result)==0:
        print(-1)
    else:
        print(result[0])
    
chonsu()