(프로그래머스) 네트워크

문제 링크

• 프로그래머스

요약

• BFS 는 queue 를 활용하자.

기출

• 2026년 상반기 새마을금고 중앙회 코테에서 거의 비슷한 문제가 나왔다. 이거 풀어보고 갔으면 맞추는거였는데

최종 §

결과

• Unlinked node group의 개수를 구하면 되는 문젠데, 그냥 visited 추적하고 queue 만들어서 BFS 돌리면 된다.
  • 이때 queue 가 채워지고 비워지는 사이클이 몇번 수행되냐가 총 네트워크의 개수가 된다.

#include <string>
#include <vector>
#include <queue>
#include <set>
 
using namespace std;
 
int solution(int n, vector<vector<int>> computers) {
	set<int> visited;
	queue<int> q;
	int cnt = 0;
 
	for (int i = 0; i < n; i++) {
		if (visited.find(i) != visited.end()) {
			continue;
		}
 
		q.push(i);
		visited.insert(i);
 
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
 
			for (int j = 0; j < n; j++) {
				if (computers[cur][j]) {
					if (visited.find(j) == visited.end()) {
						q.push(j);
						visited.insert(j);
					}
				}
			}
		}
 
		cnt++;
	}
 
	return cnt;
}