BaekJoon 11724번: 연결 요소의 개수(C++)

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

11724번: 연결 요소의 개수

풀이법

1) DFS를 활용하면 쉽게 풀 수 있는 문제이다

2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다.

3) 연결된 Node가 총 몇 덩이인지 파악하기 위해 cnt 변수를 두어 개수를 셀 수 있게 하였다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;

int n, m;
int arr[1001][1001];
bool visit[1001];
int cnt = 0;
void dfs(int i)
{
	stack<int> st;
	st.push(i);
	visit[i] = true;

	while (!st.empty())
	{
		int now = st.top();
		st.pop();
		
		for (int j = 1; j <= n; j++)
		{
			if (visit[j])
				continue;
			if (!visit[j] && arr[now][j] == 1)
			{
				visit[j] = true;
				st.push(j);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		if (visit[i])
			continue;
		else
		{
			cnt++;
			dfs(i);
		}
	}
	cout << cnt;
}
	

간단하게 구현이 가능한 문제였으며, Sliver 2치고는 쉬웠다고 생각한다.

직접 코드를 보며 이해가 안되는 부분을 확인한다면, 이 글을 읽는 모두가 이해할 수 있을 것이라 생각한다.