[백준]2644번 촌수계산 (Python/파이썬)

1. 문제

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

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

---

2. 입/출력 설명

1) 입력

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

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

 

2) 출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다.

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

 

🎈  전체 node의 수 n, 전체 edge의 수 m

🎈  주어진 node1, node2 사이의 edge의 개수가 촌수가 됩니다.

 

💡 입력 노드 사이의 edge 개수를 출력하고, 두 노드를 연결하는 edge가 없다면 -1을 출력

---

3. Test case

사이트에서 주어진 예제 01과 02의 부모-자식 그래프를 그리면 아래와 같습니다.

1) 예제 01 & 02

### Example 01
# Input
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

# Output : 3

 

빨간 edge를 거쳐 입력 노드인 7부터 시작해 3까지 탐색을 수행합니다.

 

예제 01의 입력인 7과 3 사이의 촌수는 7 → 2 → 1 → 3까지 노드 탐색을 하며 거친 edge의 수입니다. 

그림의 빨간 edge의 수, 3이 노드 7과 3 사이의 촌수이므로 3을 출력합니다.

 

### Example 02
# Input
9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

# Output : -1

 

입력 노드인 8과 6 사이를 연결하는 edge는 없습니다.

 

그러나 두 번째 예제에서 입력된 8과 6은 두 노드 사이를 연결하는 edge가 없습니다.

따라서, 둘 사이의 촌수는 -1이 출력됩니다.

 

2) 반례 (테스트용)

# Input
13
13 7
11
1 2
1 3
1 4
4 5
4 6
6 7
2 11
11 12
12 13
8 9
9 10

# Output : 7

 

13과 7 사이를 연결하는 edge(빨간 선)의 수가 촌수가 된다.

 

예제 01, 02에서는 정상 동작하는 코드도 사이트에 제출하면 틀렸습니다가 나올 수 있습니다.

그래프에 숫자가 뒤섞여 있고, 노드 수가 더 많은 반례를 직접 만들어서 테스트했습니다.

 

13, 7의 촌수를 출력했을 때, 실제로 아래의 잘못 작성한 코드에서는 오류가 발생했습니다.

위의 반례를 입력했을 때, 그림의 빨간 선(두 노드 사이의 edge)의 개수인 7이 출력되어야 합니다.

---

4. 제출 코드

1) 정답 코드

from collections import defaultdict

def dfs(curr_node, dest_node, chon, visited=[]):
    need_visited = graph[curr_node]
    chon += 1
    visited.append(curr_node)
    
    # Debugging
    #print("curr node {}".format(curr_node))
    #print(chon)
    #print()

    if dest_node in graph[curr_node]:
        print(chon)
        exit()

    else:
        for n in need_visited:
            if n not in visited:
                dfs(n, dest_node, chon, visited)


### Main ###
N = int(input())
node1, node2 = map(int, input().split())
M = int(input())

graph = defaultdict(list)
for _ in range(M):
    key, val = map(int, input().split())
    graph[key].append(val)
    graph[val].append(key)

visited = []

dfs(curr_node=node1, dest_node=node2, chon=0, visited=visited)
print(-1)

 

깊이 우선 탐색(depth-first search, DFS)을 사용하여 촌수 계산 함수를 구현했습니다.

current node(curr_node)의 parent/child node들을 타고 들어가 destination node(dest_node)에 도달할 때까지의 edge 수인 chon을 출력합니다.

2) 오답 코드

from collections import defaultdict

def dfs(curr_node, dest_node, visited=[]):
    global chon
    chon += 1

    need_visited = graph[curr_node]
    visited.append(curr_node)

    # Debugging
    #print("curr node {}".format(curr_node))
    #print(chon)
    #print()

    if dest_node in graph[curr_node]:
        print(chon)
        exit()

    else:
        for n in need_visited:
            if n not in visited:
                dfs(n, dest_node, visited)


### Main ###
N = int(input())
node1, node2 = map(int, input().split())
M = int(input())

graph = defaultdict(list)
for _ in range(M):
    key, val = map(int, input().split())
    graph[key].append(val)
    graph[val].append(key)

visited = []
chon = 0

dfs(curr_node=node1, dest_node=node2, visited=visited)
print(-1)

 

위의 반례에서 오답을 출력한 잘못된 코드입니다.

chon을 global variable로 선언하여 함수 입력으로 받지 않고 계산하는 코드입니다.

주어진 예제에서는 정답을 출력하지만, 반례와 같이 같은 level의 노드를 여러 개 탐색해서 dest_node를 찾아야 할 때 잘못된 노드에서도 촌수가 count 되어서 오답을 출력합니다.

 

DFS 함수에서 cnt는 global이 아닌, input parameter로 사용해야 오답을 피할 수 있습니다.

---

문제 출처

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

2644번: 촌수계산