[BOJ] 1976 여행 가자 C++

개요

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

골드4 난이도 문제다.

풀이

노드간 연결 여부를 확인하는 문제다.

BFS를 통해 풀 수도 있겠지만 이번에는 유니온 파인드(disjoint-set)를 이용했다.

같은 경로의 경우 같은 루트 노드를 갖고 있으므로 이를 비교하면 된다.

기본적인 유니온 파인드로 구현이 가능했다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N_LIMIT = 202;

int parent[N_LIMIT];
int N, M;

void Init(int n)
{
	for (int i = 1; i <= n; i++)
		parent[i] = i;
}
int Find(int n)
{
	if (parent[n] == n) return n;

	return parent[n] = Find(parent[n]);
}
void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (a == b) return;
	parent[a] = b;
}
void Solution()
{
	cin >> N >> M;
	Init(N);

	int num;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> num;
			if (num) Union(i, j);
		}
	}

	cin >> num;
	int root = Find(num);
	for (int i = 2; i <= M; i++)
	{
		cin >> num;
		if (root != Find(num))
		{
			cout << "NO";
			return;
		}
	}
	cout << "YES";
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	Solution();
}