[Python] BOJ/백준 11724번 연결 요소의 개수

[문제]

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

11724번: 연결 요소의 개수

 

[풀이]

연결요소(Connected Component)란?

그래프는 위의 그림처럼 간선이 존재하지 않아 여러 개로 나누어 있을 수 있다. 이것을 두 개의 그래프로도 볼 수 있지만, 하나의 그리프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 나누어진 각각의 그래프를 연결 요소라고 한다. 연결 요소가 될 조건은 아래와 같다.

1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안 된다.

위의 조건에 따라 위 그림은 2개의 연결 요소로 이루어져 있다고 할 수 있다. 연결 요소를 구하는 방법은 DFS나 BFS 탐색을 통해 할 수 있다.

---

 

 

 

 

옆의 그림과 같이 예제 1은 2개의 연결 요소로 이루어져 있고,

예제 2는 1개의 연결 요소로 이루어져 있다.

 

 

 

 

BFS 알고리즘의 풀이는

2021.08.18 - [BOJ] - [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙과 비슷하다.

[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)