[백준/BOJ] 2644번 : 촌수 계산 _Python

2644번: 촌수계산

 

>문제

>접근방법

   친척 관계를 그래프라고 생각하고 방문할 때마다 방문하기 이전 노드의 방문 횟수를 쌓아간다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

import sys
# 런타임에러(재귀오류) 방지용 코드
sys.setrecursionlimit(10**6)

# 전체 사람 수 입력 받기
n = int(input())
# 촌수를 계산 할 두 사람의 번호 입력 받기
a, b = map(int, input().split())
# 부모자식들 간의 관계 개수 입력 받기
m = int(input())
# 가족관계를 입력할 리스트 생성
fam = [[] for _ in range(n+1)]
# 방문 확인용 리스트
visit = [0]*(n+1)

# 가족관계 입력 받기
for _ in range(m):
    n1, n2 = map(int, input().split())
    fam[n1].append(n2)
    fam[n2].append(n1)

# 촌수 계산하는 함수
def dfs(s):
	# 연결된 모든 노드 방문
    for i in fam[s]:
    	# 노드가 아직 방문 전이면
        if visit[i] == 0:
        	# 이미 방문된 노드의 방문횟수만큼 더하기
            visit[i] = visit[s]+1
            # 위 과정을 재귀
            dfs(i)

dfs(a)
# 관계가 있으면(0 이상이면) 출력, 없으면 -1 출력
print(visit[b] if visit[b]>0 else -1)

 

 

>결과

 

 

>결론 

풀고 나서 일주일만에 쓰는거라 기억이 복구하는데 오래 걸렸다. 뇌가 굳었다. 콜록콜록