BOJ 11724 - 연결 요소의 개수

연결 요소의 개수 - 🥈 Silver 2

• 문제 링크
  https://www.acmicpc.net/problem/11724

무향 그래프(undirected graph)에서의 연결 요소의 개수를 구하는 것이 이 문제의 목적이다. 연결 요소는 간단하게 DFS 혹은 BFS로 해결할 수 있다.

우선 그래프를 인접 리스트로 표현하기 위해 2차원 배열(혹은 vector)를 생성하여 간선에 대한 정보를 저장한다. 그리고 아래와 같이 DFS 혹은 BFS를 모든 노드에 대해 수행한다.

DFS or BFS

• 만일 해당 노드를 방문했었다면 return 0
• 방문하지 않았다면 해당 노드에 대해 DFS or BFS를 수행한 이후 return 1

위에 대한 return 값을 전부 더하면 주어진 그래프의 연결 요소의 개수가 된다. 이에 대한 풀이 코드는 아래와 같다.

풀이 코드

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

int N, M, u, v, result;
vector<int> temp;
vector<bool> visited;
vector<vector<int>> graph;

// DFS 코드
int DFS(int start) {
	// 방문한 적이 있다면 0을 return
	if (visited[start]) return 0;
    // 아닐 경우 visited 갱신 후, DFS 수행, 1을 return
	else {
		visited[start] = true;
		for (auto iter : graph[start]) {
			DFS(iter);
		}
		return 1;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
    // 입력값 저장과 초기화
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		graph.push_back(temp);
		visited.push_back(false);
	}

	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		graph[u - 1].push_back(v - 1);
		graph[v - 1].push_back(u - 1);
	}
	
    // 모든 노드에 대한 DFS 결과를 더해서 출력
	for (int i = 0; i < N; i++) {
		result += DFS(i);
	}

	cout << result << "\n";
	visited.clear();
	graph.clear();
	return 0;
}

결과