[백준] 2644번 촌수계산 Python

📃문제

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

📃입력

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

📃출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

📃예제 입력 1

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

📃예제 출력 1

3

📃예제 입력 2

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

📃예제 출력 2

-1

✏️문제 탐색하기

입력으로 사람 간의 부모 자식 관계가 주어지며 이를 기반으로 두 사람의 촌수를 계산하는 문제.

주어진 조건:

• 부모와 자식 간의 관계는 1촌.
• 두 사람 간에 촌수 관계가 없는 경우에는 -1 을 출력.

✏️알고리즘 선택

DFS를 사용해 깊이 우선 탐색 적용.
모든 노느와 간선을 한 번씩 탐색으로 O(N+M).

✏️코드 설계하기

1. 정점의 개수 N, 간선의 개수 M, 두 사람 a, b 를 입력받습니다.
2. 간선 정보를 읽어 리스트로 그래프를 구성합니다.
3. 시작 노드에서 목표 노드까지의 최단 경로를 탐색.
4. count에 촌수를 누적.
5. 목표 노드에 도달하면 촌수를 반환.
6. 모든 경로를 탐색했음에도 목표 노드에 도달하지 못하면 -1 반환.
7. 현재 노드가 목표 노드 b인 경우 촌수를 반환.
8. 반환값이 -1이 아닌 경우 상위 호출로 값을 전달.
9. DFS 탐색 결과를 출력.

✏️시도 회차 수정 사항

1회차

처음에 재귀 호출이 되고 if문에서 참이 되면 count-1을 보낼 수 있게 구현했는데 자꾸만 리턴값이 none이 나온다,,,
이유는 dfs함수가 반환값을 호출스택에 전달하지 않는다고 한다.. 즉 return count-1가 다음 재귀 호출로 이어지지 않고 none을 반환함.

def dfs(v, count):                
    visited[v] = True             
    count += 1                    
    if v == b:                    
        return count - 1          
    for i in list_[v]:            
        if not visited[i]:        
            dfs(i, count)   

✏️코드 구현

import sys


sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
M = int(sys.stdin.readline())

list_ = [[] for _ in range(N+1)]

for _ in range(M):
    x, y = list(map(int, sys.stdin.readline().split()))
    list_[x].append(y)
    list_[y].append(x)

visited = [False for _ in range(N+1)]


def dfs(v, count):
    visited[v] = True
    count += 1
    if v == b:
        return count - 1
    for i in list_[v]:
        if not visited[i]:
            val = dfs(i, count)
            if val != -1:
                return val
    return -1


result = dfs(a, 0)
print(result)