연결 요소의 개수
문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (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알고리즘 분류
💯 문제 풀이
🔓 문제 접근 과정
이 문제는 처음에 이해하는것이 힘들었다.
문제에 대해 간단히 설명하자면
첫번째 줄에는 정점의 개수와 간선의 개수가 주어지고
두번째 줄부터 양 끝점이 주어지는데
몇개의 트리가 구성되는지를 확인하는 것이다.
예제 입력 1로 예시를 들자면
이런식으로 되어서 2개의 트리(연결 요소)가 있는것이다.
이제 DFS를 이용해서 개수를 확인해보자.
dfs 란 함수를 만든다.
이 함수는 방문여부를 확인하고 한 점과 연결된 정점 리스트를 순회한다.
그 정점이 방문이 안된 정점이라면 다시 dfs 함수를 실행하는 재귀함수이다.
(이 dfs 함수는 dfs를 적용해야하는 문제에서 늘 적용될 함수이므로 중요하다.)
그리고 이제 graph를 만들어야 한다.
이 그래프는 각각의 인덱스가 정점을 의미하고 그 정점과 연결된 다른 정점이 배열로 들어가있다.
예제 1의 그래프는 다음과 같다.
[[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]이러한 그래프의 각 요소를 정렬을 해주어야한다.
즉 각각의 요소에서 작은수가 앞에 있어야 한다.
이런식으로 정렬을 해주지 않으면 방문 여부를 확인할때 확인되지 않은 정점이 생길수있다.
이제 visited 란 배열을 만들어 방문 여부를 확인해준다.
dfs 함수에서 방문이 되면 True 로 만들어주고 다음 정점을 dfs해준다.
그래프 각각을 순회하면서 방문여부를 확인하며 모두 방문이 되었으면 count를 1더해주는 방식으로 하여 개수를 파악하면 된다.
🔑 최종 코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(graph, v, visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
node, line = map(int, input().split())
graph = [[] for _ in range(node+1)]
for _ in range(line):
u,v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
for i in range(node+1):
graph[i].sort()
visited = [False]*(node+1)
count = 0
for i in range(1, node+1):
if visited[i] == False:
dfs(graph, i, visited)
count += 1
print(count)