[🥈2 / 백준 11724 / 파이썬] 연결 요소의 개수

 

11724번: 연결 요소의 개수

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

예제 입력 1  6 5 1 2 2 5 5 1 3 4 4 6	예제 출력 1  2
예제 입력 2  6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	예제 출력 2  1

 

풀이

 

연결 요소(Connected Component)란, 한 그래프가 있을 때 서로 연결된 정점들의 뭉텅이이다.

 

 

위 그림의 연결 요소는 왼쪽의 3 정점, 오른쪽의 2 정점으로 총 2개이다.

 

 

만약 위와 같이 그래프의 정점이 모두 연결되었다면, 연결 요소는 1개가 된다.

연결 요소를 다른 말로 말하면 '영역'이 될 수 있겠다.

 

다시 문제로 돌아와서, 우리는 주어진 그래프의 연결 요소의 개수를 구해야 한다.

연결 요소를 구하는 방법은 DFS, BFS 아무거나 수행해도 구할 수 있다.

필자는 요즘 BFS 문제만 풀이해서 오랜만에 DFS 코드를 작성해보았다.

 

우선 정점의 간선들을 입력받아 인접 리스트를 생성한다.

그리고 해당 정점을 방문했었는지 체크하는 visited 배열을 만들고, DFS를 돌며 현재 위치한 정점의 방문 여부를 기록한다.

 

DFS 한 사이클이 끝나면, 한 연결 요소에 있는 정점들은 모두 방문 완료 기록이 남는다.이제 방문하지 않은 정점들을 다시 찾아나가며 DFS를 수행하면 된다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v):
    if visited[v] > 0:
        return
    
    visited[v] = 1
    for i in link[v]:
        dfs(i)

n,m = map(int,input().split())
visited = [0] * n

# 인접 리스트 생성
link = [[] for i in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

# r : 연결 요소의 개수
r = 0
for i in range(n):
    if visited[i] == 0:
        r += 1
        dfs(i)
        
print(r)