11724 - 연결 요소의 개수

문제요약

1. 입력으로 방향성없는 그래프가 주어진다.
2. 주어진 그래프에서의 연결요소를 구하라

# Node	# Edge
6	5

Node1	Node2
1	2
2	5
5	1
3	4
4	6

위와 같은 입력이 주어지면 아래와 같은 그래프가 생기게 된다.

여기서는 (1, 2, 5) / (3, 4, 6) 2개의 연결 요소가 존재한다.

접근법

이 문제도 전형적인 BFS를 이용하여 쉽게 풀수 있다. 그래프가 주어졌을 때 서로 연결되어 있는 노드의 묶음의 개수를 출력하면 된다. 그래프를 저장하는건 Linked List를 사용해도 좋고, 인접행렬을 사용해도 좋다. 이번 문제에서는 그래프를 저장하기 위해 Linked List를 사용하도록 하겠다. 위 그래프를 Linked List로 나타내면 다음과 같다.

Node	Connected Node
1	2, 5
2	1, 5
3	4
4	3, 6
5	1, 2
6	4

전체 6개의 노드가 있으므로 1 ~ 6까지 모든 노드를 탐색한다. 만약 n번째 노드가 지금까지 발견한 노드 묶음에 포함되어 있지 않다면 n번째 노드부터 BFS를 시작한다.

1번 노드를 탐색할 때는 지금까지 발견한 노드 묶음이 없으므로 BFS를 수행한다. 1번 노드는 2, 5번 노드와 연결되어 있으므로 현재 (1, 2, 5)가 노드 묶음이 되고 2, 5번 노드에 연결되어 있는 노드를 탐색한다. 2번 노드에 연결되어 있는 노드는 1, 5이고 5번 노드에 연결되어 있는 노드는 1, 2인데 이는 지금 발견한 노드 묶음 (1, 2, 5)에 전부 포함되기 때문에 더이상 BFS를 수행하지 않는다.

2번 노드는 지금까지 발견한 (1, 2, 5) 노드 묶음에 포함되기 때문에 BFS를 수행하지 않는다.

3번 노드는 지금까지 발견한 (1, 2, 5) 노드 묶음에 포함되지 않기 때문에 BFS를 수행한다. 3번 노드는 4번 노드와 연결되어 있으므로 (3, 4)가 노드 묶음이 되고 4번 노드는 3, 6번 노드와 연결되어 있는데 3번 노드는 (3, 4) 노드 묶음에 포함되어 있기 때문에 BFS를 수행하지 않고 6은 (3, 4) 노드 묶음에 포함되지 않기 때문에 노드 묶음에 포함시켜주고 BFS를 수행한다. 6번 노드에 연결된 4번 노드는 지금까지 발견한 (3, 4, 6) 노드 묶음에 포함되기 때문에 더이상 BFS를 수행하지 않는다.

4, 6번 노드는 (3, 4, 6) 노드 묶음에 포함되기 때문에 BFS를 수행하지 않는다.

5번 노드는 (1, 2, 5) 노드 묶음에 포함되기 때문에 BFS를 수행하지 않는다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)