[백준] 2644: 촌수계산 python 구현 / DFS

문제

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

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

 

입력을 그림으로 설명하면 다음과 같다.

 

풀이

1. 입력 받기
   • 입력에서 요구한 두 사람의 촌수가 꼭 부모, 자식 관계로 나오지 않기 때문에 양방향으로 노드를 추가 하여야 한다
2. DFS 구현
   • 본 과제에서는 깊이 우선 탐색으로 구현하는 것이 더 적합하다고 판단하였음
   • 탐색 노드와 target 노드가 같아지면 종료
   • 이후에는 더 깊이 탐색을 할 필요가 없기 때문에 result 변수에 cnt 값을 저장하고, 가지치기의 개념으로 for loop 안에 if 문을 추가하여 result의 bool 값에 따라 pass 하도록 설계 !
   • 또한, 만약 잘못된 노드로 진입 시 cnt -1을 해주어야 함
   • 마지막으로, global 변수를 잘 설정할 것!
     • 처음에 result를 global로 주지 않았다가, result를 로컬 변수로써 사용하게 되었고 result = cnt 라는 코드가 얕은 복사되어 결과값에 영향을 미쳤다.
3. 출력

 

CODE

import sys

n = int(input())
inp, target = map(int, input().split())
m = int(input()) # 부모 자식 간의 관계의 개수 
family_list = [[] for _ in range(n+1)]
for _ in range(m):
    pa, son = map(int, sys.stdin.readline().split())
    family_list[pa].append(son)
    family_list[son].append(pa)

vst = [0] * (n+1)
cnt = 0
result = 0
def dfs(current):
    global cnt, result

    if current == target:
        result = cnt
        return
    
    for child in family_list[current]:
        if result: continue
        if vst[child]: continue
        cnt += 1
        vst[child] = 1
        dfs(child)
        cnt -= 1

vst[inp] = 1
dfs(inp)

print(result if result else -1)