[백준 / C언어] 11724번: 연결 요소의 개수 (DFS로 풀이)

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

11724번: 연결 요소의 개수

 

난이도: solved.ac 실버 2

 

알고리즘 분류

---

그래프 탐색, DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

 

구현

---

노드를 방문하면 visited에서 해당 노드의 값을 1로 바꾸고, 해당 노드와 연결된 다른 노드로 DFS 함수를 통해 탐색하였다.

그리고 더 이상 연결된 노드가 없을 때까지 DFS 함수를 재귀호출하도록 하였다.

연결된 노드가 더 이상 없으면 cnt 값을 1 증가시켜 주었다.

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 1001

int coord[MAX][MAX];
int visited[MAX];
int N, M;
void DFS(int V);

int main() {
	int a, b, i;
	scanf("%d %d", &N, &M);

	for (i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		coord[a][b] = 1;
		coord[b][a] = 1;
	}

	int cnt = 0;
	for (i = 1; i <= N; i++) {
		if (!visited[i]) {
			DFS(i);
			cnt++;
		}
	}

	printf("%d", cnt);
	return 0;
}

void DFS(int V) {
	visited[V] = 1;
	for (int i = 1; i <= N; i++)
		if (coord[V][i] && !visited[i])
			DFS(i);
}