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

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다.

예제로 입력된 요소들의 연결되어있는 개수를 출력하는 문제

6 5
1 2
2 5
5 1
3 4
4 6

위의 예제를 대입해보면

6개의 정점과 5개의 간선의 개수가 주어졌다

1->2번과 연결되었고 2->5번과 연결 1->5번이 연결됐으니 1 2 5는 이어져있다.

반면 3->4와 4->6은 서로 연결은 되어있지만 1 2 5와는 연결 안됐으니 

총 연결 요소 덩어리는 2개 출력결과가 2가 나와야 한다

 

문제의 접근방식은 DFS로 풀어봤다.

 

그래프에서 같은 부분을 탐색하고 방문처리를 하고

1차적으로 탐색된 방문 배열을 기반으로 방문이 안된 false 배열값을 재 탐색한다,

재탐색하기전에 count변수 값을 더해주면 모든 방문배열이 true가 될때까지 

몇번의 dfs를 했는지 즉, 몇개의 덩어리가 나왔는지 확인해준다

 

코드는 아래와 같다.

import sys
sys.setrecursionlimit(10000)

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        if not visited[e]:
            dfs(e)
            
N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
count = 0

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
    
for j in range(1, N + 1):
    if not visited[j]:
        dfs(j)
        count += 1

print(count)