[문제]
https://www.acmicpc.net/problem/11724
[풀이]
연결요소(Connected Component)란?
그래프는 위의 그림처럼 간선이 존재하지 않아 여러 개로 나누어 있을 수 있다. 이것을 두 개의 그래프로도 볼 수 있지만, 하나의 그리프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 나누어진 각각의 그래프를 연결 요소라고 한다. 연결 요소가 될 조건은 아래와 같다.
- 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
- 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안 된다.
위의 조건에 따라 위 그림은 2개의 연결 요소로 이루어져 있다고 할 수 있다. 연결 요소를 구하는 방법은 DFS나 BFS 탐색을 통해 할 수 있다.
옆의 그림과 같이 예제 1은 2개의 연결 요소로 이루어져 있고,
예제 2는 1개의 연결 요소로 이루어져 있다.
BFS 알고리즘의 풀이는
2021.08.18 - [BOJ] - [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙과 비슷하다.
예제 1의 BFS 함수 진행 과정을 그려보았다.
BFS 함수
처음 선택했던 정점과 이어져있으면 이어져있는 정점을 visited 인덱스로 찾아 값을 1로 바꿔준다.
처음 선택했던 1과 [2, 5]가 연결되어 있는데 이전에 정점 2, 5에 방문한 적 없기 때문에 visited[2], visited[5] 값은 0이다.
따라서 visited[2], visited[5]를 1로 바꿔주고 queue에 각각 추가한다.
위 방법으로 1과 연결된 연결 요소 1개를 다 도는 것이다.
main 함수
main 함수에서는 for문을 통해 정점 1부터 n까지 순서대로 돈다.
만약 visited[i]가 0이라면 아직 방문하지 않았기 때문에 BFS 함수를 호출해주고,
0이 아닐 경우 이미 다른 연결 요소와 연결되어 있는 정점이기 때문에 아무것도 하지 않는다.
결론적으로 다른 연결 요소와 연결되어 있지 않았을 때 BFS 함수를 호출하고, BFS 함수를 호출할 때마다 result 변수가 1 더해지기 때문에 최종적으로는 연결 요소의 개수가 나오게 된다.
[코드]
import sys
from collections import deque
def bfs(v):
queue = deque()
queue.append(v)
while queue:
a = queue.popleft()
for i in graph[a]:
if visited[i] == 0:
queue.append(i)
visited[i] = 1
if __name__ == '__main__':
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
result = 0
visited = [0] * (n + 1)
for i in range(1, n+1):
if visited[i] == 0:
bfs(i)
result += 1
print(result)
'문제풀이 > BOJ' 카테고리의 다른 글
[Python] BOJ/백준 11279번 최대 힙 (0) | 2021.08.28 |
---|---|
[Python] BOJ/백준 1927번 최소 힙 (0) | 2021.08.28 |
[Python] BOJ/백준 18870번 좌표 압축 (0) | 2021.08.25 |
[Python] BOJ/백준 1931번 회의실 배정 (0) | 2021.08.24 |
[Python] BOJ/백준 11399번 ATM (0) | 2021.08.23 |