[BOJ] 11724 연결 요소의 개수 (DFS)

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

Note

자료구조 책에서 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이 될 때까지 반복

소스코드

#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;
}

2019-01-01 16:58:12에 Tistory에서 작성되었습니다.