Problem

문제 설명

방향 그래프에서 양방향으로 연결된 두 개의 노드를 연합 관계라고 할 때, 연합의 개수를 출력한다.

• 중간 노드 없이 직접 연결된 경우만 연합 관계라고 한다.
• 연합에 속하지 않은 노드 A가 기존 연합에 속한 노드 B와 연합 관계가 되었을 때, A는 B의 연합에 포함된다.

Submitted Code

Python

 1 N, M = map(int, input().split())
 2 maps = {i: {j: 0 for j in range(1, N + 1)} for i in range(1, N + 1)}
 3 union_group = {i: [i] for i in range(1, N + 1)}
 4 union_node = [i for i in range(N + 1)]
 5 for _ in range(M):
 6     node1, node2 = map(int, input().split())
 7     maps[node1][node2] = 1
 8     if not maps[node2][node1]:
 9         continue
10
11     # 양방향으로 연결된 경우	
12     min_idx = min(union_node[node1], union_node[node2])
13     max_idx = max(union_node[node1], union_node[node2])
14     if min_idx == max_idx:
15         continue
16     for node in union_group[min_idx]:
17         union_node[node] = max_idx
18     union_group[max_idx] += union_group[min_idx]
19     union_group[min_idx] = []
20
21 print(len([group for group in union_group.values() if len(group)]))

Line 1

노드의 개수 N과 에지의 개수 M을 입력받는다.

Line 2

연결 리스트 maps를 0으로 초기화한다.

Line 3-4

노드 번호와 연합 번호를 빠르게 탐색할 hash table을 초기화한다.

• 연합 번호를 입력 → union_group → 해당 연합에 속한 노드를 출력
• 노드 번호를 입력 → union_node → 해당 노드가 속한 연합 번호를 출력

다른 노드와 연합을 결성하지 않는 노드도 각각 하나의 연합에 속해있는 것으로 보기 때문에, 노드 번호와 같은 연합 번호에 속해 있도록 초기화했다.

Line 5

에지의 개수 M만큼 반복문을 시행한다.

Line 6-7

node1과 node2에 각각 출발 노드와 도착 노드의 번호를 입력받고, 연결 리스트 maps에 두 노드의 연결을 입력한다.

Line 8-9

역방향의 연결이 존재하는지 확인하고, 없다면 이후 코드를 실행하지 않고 for문의 다음 iterator를 실행한다.

Line 11-19

두 노드가 연합이 되었을 때, 다음과 같이 네 가지 경우를 고려해야 한다.

	node1의 연합이 없을 때	node1가 이미 연합에 속해 있을 때
node2의 연합이 없을 때	Case 1	Case 2
node2가 이미 연합에 속해 있을 때	Case 3	Case 4

• Case 1: 새로운 연합에 두 노드를 넣는다.
• Case 2-3: 기존 연합에 연합이 없는 노드를 넣는다.
• Case 4: 첫 번째 연합의 다른 노드들도 모두 두 번째 연합 소속으로 바꿔야 한다.

하지만, Line 3-4에서 노드가 각각 연합에 속해있도록 초기화 했기 때문에 Case 4만 고려한다.

Line 12-13

node1과 node2가 속한 연합 번호 중 작은 번호를 min_idx에 대입하고 큰 번호를 max_idx에 대입한다.

• 두 연합을 번호가 큰 연합으로 통합하도록 설정했다.

Line 14-15

이때, 두 노드가 속한 연합 번호가 같을 때는 이후 코드를 실행하지 않고 for문의 다음 iterator를 실행한다.

• 양방향으로 이동할 수 있는 노드들이 사이클 형태로 연결되는 경우를 예외 처리했다.
  • Line 19에서 min_idx의 목록을 초기화하는 과정이 있기 때문에 유지해야할 연합이 삭제되는 경우가 발생한다.

Line 16-19

min_idx 연합에 속한 노드들을 max_idx로 변경한다.

• 노드별 연합 번호 union_node를 max_idx로 업데이트한다.
• 연합의 노드 번호 union_group에서 min_idx 연합을 max_idx로 추가하고, min_idx 연합은 초기화한다.

Line 21

N개의 연합 중 소속된 노드 개수가 1개 이상인 연합의 개수를 출력한다.

Challendge Review

생각만큼 코드가 빠르게 정리되지 않는다. 조건 정리를 간단하게 하는 습관을 만들자.