[백준/C++] 11724번 연결요소의 개수 정답&풀이

■문제

dfs를 이용하여 11724번 문제를 풀어보도록 하겠습니다.

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

 

■소스코드(정답)

	#include <iostream>
	
	using namespace std;

	bool map[1001][1001];
	bool check[1001];

	void dfs(int n,int v) {
		check[n] = true;
		for (int i = 1; i <= v; i++) {
			if (map[n][i] && !check[i]) { dfs(i,v); }
		}
	}

	int main() {
		int v, e;
		int count = 0;
		cin >> v >> e;

		for (int i = 1; i <= e; i++) {
			int a, b;
			cin >> a >> b;
			map[a][b] = true;
			map[b][a] = true;
		}
		for (int i = 1; i <= v; i++) {
			if (!check[i]) {
				count++;
				dfs(i,v);
			}
			
		}

		cout << count << '\n';
	}

■풀이

노드간 연결을 나타내는 map과 방문한 노드인지 확인하기 위한 check를 사용했습니다.

 

1. i번째 노드에 방문하지 않았다면 새로운 연결이라 생각하고 결과값에 1을 더하고 연결된 노드에 방문하며 해당 노드의  check값을 true로 만들어줍니다.

 

2. for문에 의해 모든 노드에 방문하려하지만 이미 방문한 노드들이므로 dfs를 수행하지 않습니다.

 

3. 그러다 check가 false인 i를 만나면 새로운 연결이므로 다시 1~2를 수행합니다.