알고리즘 :: 백준 :: DFS :: 11724 :: 연결 요소의 개수

Embedded June·2020년 8월 28일
0

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

문제접근

  • 그래프의 연결요소 문제는 꼭 알아둬야하는 기본 DFS, BFS 패턴 문제다.
  • 그래프의 연결요소 개수는 임의의 시작점에서 DFS를 수행한 뒤 반환 될 때마다 하나씩 카운트한 것과 같다.
  • 이것이 가능한 이유는 DFS 또는 BFS를 수행하면 하나의 부분 그래프를 모두 탐색하게 되기 때문이다.
    다음 번 시작점에서 다른 부분 그래프를 탐색하게 된다.

코드

#include <iostream>
#include <vector>
using namespace std;

static int N, M;
static vector<int> graph[1001];
static vector<bool> isVisited(1001);

void dfs(int here) {
	isVisited[here] = true;
	for (const int& there : graph[here])
		if (!isVisited[there]) dfs(there);
}

int solve() {
	int ret = 0;
	for (int start = 1; start <= N; ++start) {
		if (!isVisited[start]) {
			dfs(start);	
			ret++;	// DFS 종료하고 리턴될 때 마다 카운팅
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int start = 0, end = 0;
		cin >> start >> end;
		graph[start].push_back(end);
		graph[end].push_back(start);
	}
	cout << solve() << '\n';
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글