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

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 이번 문제는 각 컴퓨터의 직,간접적인 연결 상태를 고려하였을 때의 네트워크의 개수를 구하는 문제이다. 이 문제는 컴퓨터(노드)들이 서로 연결되어 있다는 점에서 합집합 찾기(Union-Find) 알고리즘을 이용하는 것이 좋을 것이라 생각했다. 이 알고리즘을 이용하면 각 연결된 집합마다의 대표 노드가 무엇인지를 알 수 있다. 그렇기 때문에 모든 노드들을 각각 검사하여 부모 노드(합집합을 대표할 노드)가 몇 종류 있는지 검사하여 답을 구할 수 있을 것이라 생각했다. 주어진 예제 1번은 네트워크가 2개이며 이는 1번 노드, 2번 노드 집합, 3번 노드 집합의 개수와 일치하다. 그리고 주어진 예제 2번은 네트워크가 1개이며 1번 노드, 2번 노드, 3번 노드 집합 1개의 개수와 일치하다. 이 문제를 풀기 위해 구상한 절차는 다음과 같다.

1. 부모 노드를 초기화한다. (처음에는 자기 자신이 부모 노드이다.)
2. 주어진 computers 배열을 이용하여 연결 상태를 검사한다. 이 때, 자기 자신끼리는 따로 검사할 필요가 없다.
   1. 만약 서로 이어져 있는 상태라면 이를 저장한다.
3. 모든 연결 상태를 검사하면서, 서로의 부모 노드가 다르다면 같게 해준다. 즉, 서로 이어준다.
4. 모든 노드들을 검사한다. 각 노드 별 부모 노드를 확인한 후, 부모 노드의 종류의 개수를 센다. (집합 혹은 네트워크의 개수)

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

#define MAX 211

int parentNode[MAX];            // 노드별 부모 노드 (집합의 대표 노드)
bool isParent[MAX];             // 각 노드가 부모 노드인지를 저장할 변수
vector<pair<int, int>> links;   // 노드의 연결 상태를 저장할 변수

// 해당 노드의 부모 노드를 반환하는 함수
int ParentNode(int node)
{
	if (parentNode[node] == node)
		return node;

	return parentNode[node] = ParentNode(parentNode[node]);
}

// 노드 두 개의 부모 노드가 서로 같은지 검사하는 함수
bool IsSame(int a, int b)
{
	a = ParentNode(a);
	b = ParentNode(b);

	if (a == b)
		return true;
	else
		return false;
}

// 노드 두 개의 부모 노드를 같게 만드는 함수
void MakeSame(int a, int b)
{
	a = ParentNode(a);
	b = ParentNode(b);

	if (a < b)
		parentNode[b] = a;
	else
		parentNode[a] = b;
}

int solution(int n, vector<vector<int>> computers)
{
	int networkNum = 0;
    
    // 1. 부모 노드를 초기화한다. (처음에는 자기 자신이 부모 노드이다.)
	for (int node = 0; node < MAX; ++node)
		parentNode[node] = node;
    
    // 2. 주어진 computers 배열을 이용하여 연결 상태를 검사한다.
	for (int nodeA = 0; nodeA < computers.size(); ++nodeA)
	{
		for (int nodeB = 0; nodeB < computers[nodeA].size(); ++nodeB)
		{
            // 자기 자신끼리는 따로 검사할 필요가 없다.
			if (nodeA == nodeB)
				continue;

			int linked = computers[nodeA][nodeB];
            
            // 2-1. 만약 서로 이어져 있는 상태라면 이를 저장한다.
			if (linked == 1)
				links.push_back({ nodeA, nodeB });	
		}
	}

    // 3. 모든 연결 상태를 검사하면서, 서로의 부모 노드가 다르다면 같게 해준다.
    // 즉, 서로 이어준다.
	for (int i = 0; i < links.size(); ++i)
	{   
		int nodeA = links[i].first;
		int nodeB = links[i].second;

		if (IsSame(nodeA, nodeB) == false)
			MakeSame(nodeA, nodeB);
	}
    
    // 4. 모든 노드들을 검사한다. 
    // 각 노드 별 부모 노드를 확인한 후,
    // 부모 노드의 종류의 개수를 센다. (집합 혹은 네트워크의 개수)
	for (int node = 0; node < n; ++node)
	{
		int curParentNode = ParentNode(node);
        
		if (isParent[curParentNode] == false)
		{
			isParent[curParentNode] = true;
			++networkNum;
		}
	}

	return networkNum;
}

 

 

---

Union-Find 참고: https://blog.naver.com/ndb796/221230967614