연결 요소의 개수 11724

연결 요소의 개수 11724

 

풀이코드 ( BFS )

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 11724 연결 요소의 개수

int n, m;

vector<int> adjList[1001];
queue<int> q;
bool isVisited[1001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++){
		int from, to;
		cin >> from >> to;
		adjList[from].push_back(to);
		adjList[to].push_back(from);
	}
	
	// input 이 어떤 순서로 들어올지 알 수 없기에 오름차순으로 인접 리스트를 정렬해준다.
	for(int i = 1; i <= n; i++){
		sort(adjList[i].begin(), adjList[i].end());
	}
	
	fill_n(isVisited, 1001, false);
	
	// bfs
	
	int count = 0;
	// 모든 node 로 출발점을 설정한다.
	for(int start = 1; start <= n; start++){
		// 방문했다면 생략
		if(isVisited[start]) continue;
		
		// 방문하지 않은, start 부터 bfs 시작
		q.push(start); isVisited[start] = true;
		
		while(!q.empty()){
			int currentNode = q.front();
			q.pop();
			
			for(int i = 0; i < adjList[currentNode].size(); i++){
				int nextNode = adjList[currentNode][i];
				
				// 다음 노드를 방문했었다면 생략
				if(isVisited[nextNode]) continue;
				
				// 다음 노드를 방문하지 않았다면
				q.push(nextNode);
				isVisited[nextNode] = true;
			}
		}
		count++;
	}
	cout << count << '\n';
	
}

풀이코드 ( DFS )

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 11724 연결 요소의 개수

int n, m;

vector<int> adjList[1001];
queue<int> q;
bool isVisited[1001];

int dfs(int currentNode){
	// 출발점이 처음 들어왔을 때, 방문한 적이 있으면 0 을 return 한다.
	if(isVisited[currentNode]) return 0;
	
	// 현재 방문점을 방문 체크
	isVisited[currentNode] = true;
	
	for(int i = 0; i < adjList[currentNode].size(); i++){
		int nextNode = adjList[currentNode][i];
		
		// 다음 노드가 방문한 적이 있으면 생략
		if(isVisited[nextNode]) continue;
	
		// 없으면
		dfs(nextNode);
	}
	
	return 1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++){
		int from, to;
		cin >> from >> to;
		adjList[from].push_back(to);
		adjList[to].push_back(from);
	}
	
	// input 이 어떤 순서로 들어올지 알 수 없기에 오름차순으로 인접 리스트를 정렬해준다.
	for(int i = 1; i <= n; i++){
		sort(adjList[i].begin(), adjList[i].end());
	}
	
	fill_n(isVisited, 1001, false);
	
	int count = 0;
	
	for(int i = 1; i <= n; i++){
		count += dfs(i);
	}
	cout << count << '\n';
	
}

해설

---

적용한 레시피 / 방법론 + 접근법

풀이

1. dfs 든 bfs 든 탐색이 시작되는 순간, 연결 요소의 개수는 하나 늘어난다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

 

각각 dfs, bfs 이다.