[백준 11724번 C++] 연결 요소의 개수 (BFS)

문제

문제 분석

그래프의 연결되어 있는 뭉텅이의 개수를 찾는 문제이다. 예제 입력 1을 예시로 그림을 그리면 아래와 같고 연결 요소의 개수(뭉텅이의 개수)는 2이다.

간선에 가중치가 없으므로 bfs 탐색과 dfs 탐색으로 이 문제를 해결할 수 있다.

- (dfs/bfs 구현 연습 문제)

- (전형적인 flood fill 에서 뭉텅이의 개수를 세는 유형)

정답 코드

- bfs로 구현한 코드이다.

- 이때 메모리 제한은 512MB 이므로 N의 크기가 1000인 2차원 배열을 만들어도 된다.

- 이때 1부터 입력받은 노드 개수만큼 돌면서 만약 방문하지 않은 노드가 있다면 bfs 탐색을 하고 bfs 탐색을 한 횟수가 뭉텅이의 개수이므로 그 개수를 출력해준다.

// bfs 풀이
#include <iostream>
#include <queue>
#define MAX_N 1001 // 최대 N은 1000 (2차원 배열에 할당해도 메모리 상관 없음)
using namespace std;

int Board[MAX_N][MAX_N]; // 연결되어 있으면 : 1
int visited[MAX_N]; // 방문하면 1, 방문X : 0
int node, edge;

void bfs(int start_node) {
	queue<int> q;
	// 초기노드 방문 처리
	q.push(start_node);
	visited[start_node] = 1;

	
	while (!q.empty()) {
		int cur_node = q.front();
		q.pop();

		for (int next_node = 1; next_node <= node; next_node++) {
			if (Board[cur_node][next_node] != 1) continue; // 연결되어 있지 않으면 패스
			if (visited[next_node] != 0) continue; // 이미 방문한 노드면 패스

			// 다음 노드 조건에 해당하는 것만 방문 처리
			q.push(next_node);
			visited[next_node] = 1;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> node >> edge;
	for (int i = 1; i <= edge; i++) {
		int start, end;
		cin >> start >> end;
		Board[start][end] = Board[end][start] = 1;
	}
	
	int ans = 0;
	for (int i = 1; i <= node; i++) {
		if (visited[i] == 0) {
			bfs(i);
			ans++;
		}
	}
	cout << ans;

	return 0;
}