BaekJoon 11724 연결 요소의 개수 (DFS)

 

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

소스 결과 : 2964 KB / 248 ms

출처 : BackJoon

 

설명

자료구조 책에서 DFS / BFS를 설명할 때 예시로 자주 들어지는 문제

 

방향이 없는 그래프 이기에 간선을 행렬로 저장시 간선을 양방향으로 저장

x y 가 주어진다면 xy와 yx를 둘다 등록해야 한다.

 

정점의 개수가 최대 1000개

인접 행렬 사용시 1,000 * 1,000 = 1,000,000개 = 400 만 Bytes ( int )

간선 행렬 사용시 m * 2 = n * (n - 1) / 2 * 2 = 1,000 * 999 = 999,000 = 399.6 만 Byte ( int )

둘다 3 MB 정도 밖에 사용하지 않고 차이도 별로 없기에 인접행렬을 사용한다.

 

알고리즘

1. x ,y 가 주어지면 배열의 x, y / y ,x 칸을 등록

2. 1번 행부터 시작

3. DFS 시작

4. 카운트 + 1

시작 라인이 n이 될 때까지 반복

 

BFS 버전 : https://girlfriend-yerin.tistory.com/14

 

소스코드

#include <iostream>

using namespace std;

bool adjMatrix[1000][1000];
bool check[1000];

void func(int start, int n) {

	if (check[start])
		return;

	check[start] = true;

	for (int i = 0; i < n; i++)
	{
		if (adjMatrix[start][i])
			func(i, n);
	}
}

int main()
{
	int n, m, count = 0;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;

		adjMatrix[x-1][y-1] = adjMatrix[y-1][x-1] = true;
	}

	for (int i = 0 ; i < n ; i++)
	{
		if (check[i])
			continue;

		func(i, n);
		count++;
	}

	cout << count;

	return 0;
}