백준 2644번 촌수계산 (Python, DFS)

백준 2644번 촌수계산 문제 바로가기

문제 이해

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

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

입력

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

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

출력

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

문제 접근

이 문제는 DFS로 푸는게 좋아보인다!
그 이유는 하나의 촌수가 늘어날 때마다 그 개수를 세주어야 하는데 dfs의 인자로 현재까지의 촌수를 전해주면서 1을 더하면 촌수를 쉽게 계산할 수 있기 때문이다.

• 입력받기
• 촌수 확인하기 (DFS)

문제 풀이

입력받기

아래와 같이 N+1개의 2차원 배열 family를 생성한다.
이 family에 가족관계를 넣어둔다. 이렇게 되면 1과 1촌인 사람들이 family[1]에 들어가게 된다.
따라서 쉽게 촌수를 계산할 수 있다.

import sys
N = int(sys.stdin.readline())
a, b = map(int,sys.stdin.readline().split())
M = int(sys.stdin.readline())
family = [[] for i in range(N+1)]
for i in range(M):
    x, y = map(int, sys.stdin.readline().split())
    family[x].append(y)
    family[y].append(x)

촌수 확인하기 (DFS)

촌수 확인하기는 전형적인 dfs이다.
몇번 dfs로 타고 들어가는지를 계산하면 그것이 촌수가 된다.
따라서 dfs(val, count+1)을 통해 한 번 다른 사람으로 이동할 때 count를 증가시켜 촌수를 계산한다.
어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다. 라는 조건을 구현하기 위해 flag를 설정하여 입력에서 요구한 사람의 관계를 찾았다면 flag를 True로 만들고 count를 출력하여 최종적으로 count만 출력되도록 한다.
만약 찾지 못한다면 flag가 False이므로 count가 출력되지 않고 -1만 출력될 것이다.

def dfs(x, count):
    global flag
    visited[x] = True
    if x==b:
        flag=True
        print(count)
    for val in family[x]:
        if visited[val] == False:
            dfs(val,count+1)

flag=False
dfs(a,0)
if flag==False:
    print(-1)

제출 코드

import sys
N = int(sys.stdin.readline())
a, b = map(int,sys.stdin.readline().split())
M = int(sys.stdin.readline())
family = [[] for i in range(N+1)]
for i in range(M):
    x, y = map(int, sys.stdin.readline().split())
    family[x].append(y)
    family[y].append(x)
visited = [False for _ in range(N+1)]
result = []
def dfs(x, count):
    global flag
    visited[x] = True
    if x==b:
        flag=True
        print(count)
    for val in family[x]:
        if visited[val] == False:
            dfs(val,count+1)

flag=False
dfs(a,0)
if flag==False:
    print(-1)