백준/1976/graph(union_find)/여행 가자

백준/1976/graph(union_find)/여행 가자

문제 해석

동혁이가 짠 여행 플랜대로 도시를 방문할 수 있는지를 확인하는 문제입니다.

문제 풀이

즉, 모든 도시들이 연결되어 하나의 거점 도시를 공유할 수 있게 문제를 풀어봤습니다.
이 거점 도시를 동혁이의 여행플랜에 포함된 도시들이 공유하고 있다는 것은 곧 모든 도시가 연결되어 있다는 뜻이고, 동혁이는 여행을 성공적으로 할 수 있다는 말이됩니다.

int find_parents(int num)
{
	if (city_parents[num] == num)return num;
	return city_parents[num] = find_parents(city_parents[num]);
}

void union_make(int u, int v)
{
	u = find_parents(u); v = find_parents(v);
	if (u == v)return;
	if (u > v)city_parents[u] = v;
	else city_parents[v] = u;
}

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

for (int i = 1;i <= N;i++)
{
	for (int j = 1;j <= N;j++)
	{
		int _connected = 0;
		cin >> _connected;
		if (_connected == 1)
		{
			union_make(i, j);
		}
	}
}

우선 도시들이 서로 같은 도시군을 점유 하고 있는지 부터 확인하며, 서로 이어져 있는 도시는 같은 도시군에 포함 시킵니다. 이 때, 도시를 표현하는 숫자가 낮을 수록 도시군을 대표하는 거점 도시로 만들기로 합니다.

for (int i = 1;i <= N;i++)
{
	find_parents(i);
}

이 후, 모든 도시가 해당 거점 도시를 대표 도시로 가질 수 있게 다시 한번 find_parents 함수를 돌립니다. find_parents 함수로 인해 결국 각각의 도시의 대표도시는 가장 낮은 숫자로 표현되게 됩니다.

::sort(travel_city.begin(), travel_city.end());

이렇게 준비가 완료되면 동혁이의 플랜 중 가장 낮은 도시(낮은 도시를 뽑아야 해당 도시를 대표 도시로 탐색 해볼 수 있기 때문)

int compared_city = city_parents[travel_city[0]];

for (int _city : travel_city)
{
	if (city_parents[_city] != compared_city)
	{
		flag = false;
	}
}

대표격인 도시를 여행할 도시들의 대표 도시와 비교하면서 맞는지 확인하고 다른 도시군이 나올 경우 이 여행 플랜은 실패이기 때문에 NO를 출력하고 for문을 다 돌고 나오면 여행 플랜은 성공한거기 때문에 YES를 출력해줍니다.
( 이 때 대표 선정 도시를 전체 도시에서 뽑아와서 첫번째 풀이는 실패했습니다.)

풀이

첫번째 풀이(부모 도시 선정 오류(user error))

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

int city_parents[201];
vector<int> travel_city;

int find_parents(int num)
{
	if (city_parents[num] == num)return num;
	return city_parents[num] = find_parents(city_parents[num]);
}

void union_make(int u, int v)
{
	u = find_parents(u); v = find_parents(v);
	if (u == v)return;
	if (u > v)city_parents[u] = v;
	else city_parents[v] = u;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// N은 200이하 N은 도시의 수, M은 여행 계획에 속한 도시의 수
	int N, M = 0;
	cin >> N >> M;

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

	for (int i = 1;i <= N;i++)
	{
		for (int j = 1;j <= N;j++)
		{
			int _connected = 0;
			cin >> _connected;
			if (_connected == 1)
			{
				union_make(i, j);
			}
		}
	}

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

	for (int i = 1;i <= N;i++)
	{
		find_parents(i);
	}

	bool flag = true;

	::sort(travel_city.begin(), travel_city.end());

	int compared_city = city_parents[0];

	for (int _city : travel_city)
	{
		if (city_parents[_city] != compared_city)
		{
			flag = false;
		}
	}

	if (!flag)
	{
		cout << "NO\n";
	}
	else
	{
		cout << "YES\n";
	}

	return 0;
}

두번째 풀이

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

int city_parents[201];
vector<int> travel_city;

int find_parents(int num)
{
	if (city_parents[num] == num)return num;
	return city_parents[num] = find_parents(city_parents[num]);
}

void union_make(int u, int v)
{
	u = find_parents(u); v = find_parents(v);
	if (u == v)return;
	if (u > v)city_parents[u] = v;
	else city_parents[v] = u;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// N은 200이하 N은 도시의 수, M은 여행 계획에 속한 도시의 수
	int N, M = 0;
	cin >> N >> M;

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

	for (int i = 1;i <= N;i++)
	{
		for (int j = 1;j <= N;j++)
		{
			int _connected = 0;
			cin >> _connected;
			if (_connected == 1)
			{
				union_make(i, j);
			}
		}
	}

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

	for (int i = 1;i <= N;i++)
	{
		find_parents(i);
	}

	bool flag = true;

	::sort(travel_city.begin(), travel_city.end());

	int compared_city = city_parents[travel_city[0]];

	for (int _city : travel_city)
	{
		if (city_parents[_city] != compared_city)
		{
			flag = false;
		}
	}

	if (!flag)
	{
		cout << "NO\n";
	}
	else
	{
		cout << "YES\n";
	}

	return 0;
}