[프로그래머스 Level 3] 네트워크(C++)

코딩테스트 연습 - 네트워크 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

연결된 컴퓨터를 그룹으로 묶어주고 그룹의 개수를 세주는 문제이다. 즉 전형적인 union-find 문제이다.

 

#include <string>
#include <vector>

using namespace std;
int parent[200];

int findParent(int node) {
	if (parent[node] == node) {
		return node;
	}
	return parent[node] = findParent(parent[node]);
}

void unionNode(int x, int y) {
	int p1 = findParent(x);
	int p2 = findParent(y);
	if (p1 > p2) {
		parent[p2] = p1;
	}
	else {
		parent[p1] = p2;
	}
}

int checked[200];

int solution(int n, vector<vector<int>> computers) {
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	int answer = 0;
	for (int i = 0; i < computers.size(); i++) {
		for (int j = 0; j < computers[i].size(); j++) {
			if (j != i && computers[i][j] == 1) {
				unionNode(i, j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (!checked[findParent(i)]) {
			answer++;
			checked[findParent(i)] = true;
		}
	}
	return answer;
}