<백준 알고리즘> 분리집합 1976번

분리집합(Disjoint-Set)

분리집합이란 서로 중복되지 않는 집합이며 그 집합이 전체 집합 U를 구성하고 있는 집합을 의미한다.

만약 어떤 집합이 그래프로 이루어져 있고 우리가 찾고자 하는 대상이 그 안에 속해 있는지 확인 하기위해 여러 탐색을 써서 찾을 수 있을 것이다. 그러나 매번 탐색을 하여 찾으면 효율적이지 않기에 한 집합이 공통으로 갖고있는 root에 대한 판단만 하면 더 효율적으로 원하는 답을 얻을 수 있을 것이다.

<출처:hacker earth>

이 자료구조를 사용하는데 두 가지 함수가 사용된디. Find와 Union인데 각각 루트를 찾는 것과 두 집합을 병합하는데 사용되는 함수이다.

분리집합이 사용된 문제

백준 1976번

접근 방법

1.처음 봤을 땐 도시 수도 200개 밖에 안되기에 메모리도 시간도 별로 안걸릴 것 같아서 플루이드-워셜 알고리즘을 사용하여 만약에 어떤 경로를 거쳐 다른 곳으로 갈 수 있다면 city[i][j]를 1로 바꿔주었다. 그리고 자기 자신은 무조건 갈 수 있으니 나중에 다 1로 바꿔주었다.

이렇게 해서도 풀렸지만 알고리즘 분류를 보니 분리집합을 사용하는 풀이도 있다는 것을 알게 되었다.

2. 분리집합을 사용하는 경우는 만약 어떤 도시에서 다른 도시로의 길이 존재한다면 그 도시는 서로 같은 집합에 속해있는 것이기에 같은 루트를 가진다고 설정해주면 된다.

만약 길이 존재하지 않는 경우 두 도시는 서로 다른 집합에 속하기에 루트가 다를 것이므로 이를 통해 갈 수 있는지 없는지 여부를 판단하면 됐다.

플루이드-워셜 코드

int main()
{
    cin >> N >> M;


	for (int i = 1; i <= N ; i++)
	{
		for (int j = 1; j <= N; j++) 
		{
			cin >> city[i][j];
			
		}
	}

	for (int i = 0; i < M; i++)
	{
		int c;
		cin >> c;
		cityplan.push_back(c);
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++) 
		{
			for (int j = 1; j <= N; j++)
			{
		
				if (city[i][k] + city[k][j] == 2)
					city[i][j] = 1;
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		city[i][i] = 1;
	}

	bool isTravel = true;
	

	for (int i = 0; i < cityplan.size() - 1 ; i++)
	{
		int curCity = cityplan[i];
		int nextCity = cityplan[i + 1];

		if (city[curCity][nextCity] == 0)
		{
			isTravel = false;
			break;
		}
	}

	if (isTravel)
	{
		cout << "YES";
	}
	else
	{
		cout << "NO";
	}

    return 0;
}

분리집합 이용 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

int N,M;

int city[201][201] = { 0 };
vector<int> cityplan;

int uniV[201] = { 0 };

int find(int v)//재귀함수를 통해 루트까지 이동하여 루트를 받아옴
{
	if (v == uniV[v])
		return v; //만약 루트일 경우 루트의 부모는 루트이므로 루트를 반환

	uniV[v] = find(uniV[v]);
	return uniV[v];
}

void Union(int v1, int v2)
{
	v1 = find(v1);
	v2 = find(v2);

	if (v1 < v2) uniV[v2] = v1; //병합할때 두 루트의 크기를 비교해서 병합(높이나 level을 이용하는 것처럼)
	else uniV[v1] = v2;
}


int main()
{
    cin >> N >> M;


	for (int i = 1; i <= N ; i++)
	{
		for (int j = 1; j <= N; j++) 
		{
			cin >> city[i][j];
			
		}
	}

	for (int i = 1; i <= N; i++)
	{
		uniV[i] = i; //처음엔 루트를 다 자기자신으로 설정
	}

	for (int i = 0; i < M; i++)
	{
		int c;
		cin >> c;
		cityplan.push_back(c);
	}

	
	for (int i = 1; i <= N; i++) 
	{
		for (int j = 1; j <= N; j++)
		{
	
			if (city[i][j] == 1 && (uniV[i] != uniV[j])) //만약 길이 있으면서 루트가 다를경우 병합해줌.
				Union(i, j);
		}
	}
	
	int startCity = uniV[cityplan[0]];

	bool isTravel = true;
	

	for (int i = 1; i < cityplan.size() ; i++)
	{
		if (startCity != uniV[cityplan[i]]) //루트가 다를 경우 갈 수 없다.
		{
			isTravel = false;
			break;
		}
	}

	if (isTravel)
	{
		cout << "YES";
	}
	else
	{
		cout << "NO";
	}

    return 0;
}