BOJ 1976 여행 가자

문제에서 여행 계획에 속한 도시 M이 주어지고 총 N 개의 여행 계획이 주어진다. 이때 여행계획을 달성할 수 있는지 없는지 확인하는 문제이다.

 

문제를 해결하기 위해 생각해낸 아이디어는 다음과 같다.

1. 만약 a-b-d-a-c 순서로 여행한다고 가정하였을경우 a-b, b-d, d-a, a-c 가 연결 되어있다면 무조건 갈수 있지 않을까?

2. 그럼 서로 연결되어있다는 것은 어떻게 알수 있을까? -> union - find를 활용하자!!

 

Union - Find에서 핵심은 각각의 i,j에 대해 각각 root parent를 확인하고 둘중에 더 큰 집합으로 parent를 업데이트 해준다.

 

이렇게 구한 그래프와 그의 parent 정보를 바탕으로 계획에 있는 도시들이 모두 같은 root parent를 가질경우 여행 계획을 달성할 수 있다.

#include<iostream>
#include<cstring>
using namespace std;

int arr[201];

int findParent(int x)
{
	if(arr[x]<0)
	{
		return x;
	}
	int parent = findParent(arr[x]);
	return parent;
}

void merge(int aParent, int bParent)
{
	//집합의 크기가 더 큰 쪽으로 합쳐진다
	if(abs(aParent) >= abs(bParent))
	{
		arr[aParent] += arr[bParent];
		arr[bParent] = aParent;
	}
	else
	{
		arr[bParent] += arr[aParent];
		arr[aParent] = bParent;
	}
}

int main()
{
	int n, m;
	cin >> n >> m;

	memset(arr, -1, sizeof(arr));


	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int num = 0;
			cin >> num;

			if(num == 1)
			{
				int aParent = findParent(i);
				int bParent = findParent(j);

				if(aParent == bParent)
				{
					continue;
				}

				merge(aParent, bParent);
			}
		}
	}

	int root = 0;
	for(int i = 0; i < m; i++)
	{
		int node;
		cin >> node;
		if(i != 0)
		{
			if(root != findParent(node))
			{
				cout << "NO";
				return 0;
			}
		}
		else
		{
			root = findParent(node);
		}
		
	}

	cout << "YES";
}