[백준 BOJ][C++]11724번 연결 요소의 길이 풀이: BFS/DFS

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

11724번: 연결 요소의 개수

 

 이 문제는 BFS 또는 DFS 로 해결할 수 있습니다. 

 

 저는 재귀 호출을 이용한 DFS 로 해결하였는데요! 입력된 값으로 그래프의 정보만 잘 저장하면 쉽게 풀립니다.

 

 먼저 정점의 개수 n과 간선의 개수 m을 입력으로 받은 뒤, 간선의 개수 만큼 두 정점이 연결된 간선의 정보를 받습니다.

 

 이때 입력된 두 정점 u와 v가 연결되었음을 표시해야 하는데, 2차원 배열을 사용하여 두 정점이 연결되었다면 graph[u][v] = graph[v][u] = 1로 저장합니다. 

 

 이제 아직 방문하지 않은 정점을 기준으로 그 정점에 연결된 모든 정점을 방문하는 dfs()를 호출합니다. 이 dfs()가 끝나면 연결 요소를 증가시키고 아직 방문하지 않은 정점을 찾아 다시 dfs()를 호출합니다. 

 

#include<iostream>
#include<algorithm>

using namespace std;

int n, m;

int graph[1001][1001] = { 0, };
int visit[1001] = { 0, };

void dfs(int w) {

	visit[w] = 1;

	for (int i = 1; i <= n; i++) {
		if (graph[w][i] == 1 && visit[i] == 0)
			dfs(i);
	}

}

int main(void) {

	int u, v;
	int cnt = 0;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		graph[u][v] = graph[v][u] = 1;
	}

	for (int i = 1; i <= n; i++) {
		if (visit[i] == 0) {
			dfs(i);
			cnt++;
		}
	}

	cout << cnt;

	return 0;
}