[C언어] 백준 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

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

 

 

문제 풀기 전 로직 생각하기

---

간선으로 연결되어있는 트리의 개수를 출력하는 문제입니다.

bfs 또는 dfs로 간단하게 풀 수 있는 문제인데요.

저는 dfs로 푸는게 더 쉬울 것 같아서 dfs로 풀었습니다.

 

서로 간선으로 연결 되어있는것을 인식 시키기 위해 2차원 배열로 입력을 받을 때 번갈아 가면서 카운트를 해주면 될것 같습니다.

예를 들어서 2, 6을 입력 받을 때 [2][6]++, [6][2]++ 을 해서 서로 연결되어 있음을 인식 시키면 될것 같습니다.

 

 

전체 코드

---

#include <stdio.h>

int n, m, t1, t2, node[1001][1001] = {}, visited[1001] = {};

void	dfs(int next)
{
	// 방문 체크 후 1부터  n까지 dfs 순회
	if (!visited[next] && ++visited[next])
		for (int i = 1; i <= n; i++)
			if (node[next][i])
				dfs(i);
}

int main()
{
	int	result = 0;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &t1, &t2);
        // 서로 연결 시키기
		node[t1][t2]++;
		node[t2][t1]++;
	}
	for (int i = 1; i <= n; i++)
    	// 방문한 적이 없는 노드일 때 카운트 후 dfs
		if (!visited[i] && ++result)
			dfs(i);
	printf("%d\n", result);
	return (0);
}

 

문제 해설

---

입력을 받을 때 서로 카운트를 해서 연결 시켜주고 for문으로 방문한 적이 없는 노드들을 dfs 시켜주었습니다.

맨 처음 입력 받을 때 서로 연결 시켜주었기에

dfs함수에서 단방향처럼 인식 되지 않아 오류가 나지 않게 했습니다.