[백준] 11724번 연결 요소의 개수 - C++ (DFS, 그래프)

풀이에 https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component 포스팅을 참고하였음을 밝힙니다. 

 

발상

1. 그래프 + 주어진 그래프의 정점들을 DFS를 이용해 탐색하여 연결 요소의 개수를 밝히는 문제이다. 

2. 그래프는 우선 C언어에 내장된 vector를 이용해 구현하고, 방향이 없는 그래프이므로 하나를 입력받을 때마다 v->u, u->v 두 가지 모두를 입력한다, 

3. DFS를 이용하면 한 개의 연결 요소 그래프에 속한 노드를 전부 탐색할 수 있으므로, false값을 가진 node에 대해 DFS를 수행해 해당 연결 요소의 노드를 전부 탐색하고 답에 +=1을 해준다. 그리고 또 false값을 가진 node가 있다면 이를 반복 수행해 준다. 

4. 답을 출력한다. 

 

소스코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool check[1001]; // 전역변수는 선언시 자동초기화  
vector<int> input[1001]; 

void dfs(int node){
	check[node] = true;
	for(int j=0; j<input[node].size(); j++){
		int temp = input[node][j];
		if(check[temp] == false){
			dfs(temp);
		}
	}
}
int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	
	for(int i=0; i<M; i++){
		int t1, t2;
		cin >> t1 >> t2;
		input[t1].push_back(t2);
		input[t2].push_back(t1);
	}
	
	int ans = 0;
	for(int i=1; i<=N; i++){
		if(check[i] == false){
			dfs(i);
			ans++;
		} 
	}
	cout << ans;
	return 0;
}

 

우선 vector에 간선의 정보를 넣는 과정을 살펴보면 다음과 같다.

	for(int i=0; i<M; i++){
		int t1, t2;
		cin >> t1 >> t2;
		input[t1].push_back(t2);
		input[t2].push_back(t1); //방향성이 없으므로 두 개 다 넣어주기
	}

간선의 개수만큼 for문을 돌면서 정보를 입력받고, 두 간선을 vector에 입력한다.

input[u]에 v를 (u->v). input[v]에 u를 (v->u) push_back해준다.

 

그리고 false인 node를 찾아 그 node에 대해 dfs를 수행해 주고, (해당 연결 요소에 포함된 노드는 모두 방문하게 됨.) ans++;를 수행한다. 여기서 false로 남아있는 node는 다른 연결 요소에 포함된 node인 것이다. 따라서 다시 false인 node를 찾아 dfs를 수행하는 과정을 반복해 준다. (1~N까지 수행)

	int ans = 0;
	for(int i=1; i<=N; i++){
		if(check[i] == false){
			dfs(i);
			ans++;
		} 
	}
	cout << ans;

이후 ans를 출력해 준다.

 

dfs 구현 함수 부분만 살펴보면 다음과 같다. 

void dfs(int node){
	check[node] = true;
	for(int j=0; j<input[node].size(); j++){
		int temp = input[node][j];
		if(check[temp] == false){
			dfs(temp);
		}
	}
}

dfs(깊이 우선 탐색) 에서는 node를 방문하고, 그 아래 자식 node로 방문을 이어간다. 따라서 node를 우선 true로 바꾸어 주고, 해당 node에 연결된 간선만큼 for문이 돌도록 해준 뒤 아직 방문되지 않은 자식 node에 대해 다시 dfs를 수행해 준다. (check[temp] == false를 확인하는 과정)