C++ [여행가자 - 백준] / #분리집합

Problem

---

여행가자_백준

1976번: 여행 가자

 

문제를 처음 읽었을 때 낯이 익은 느낌이었다.

이전에 공부했던 분리집합과 비슷했기 때문이다.

바로 분리집합을 적용하려 했으나 분리집합 구현 코드가 잘 떠오르지 않아 이전에 작성한 글을 읽고 풀었다.

 

2023.03.27 - [C++/알고리즘] - C++ [알고리즘] / # Union find(분리집합)

C++ [알고리즘] / # Union find(분리집합)

 

Solve

---

 

-도시의 연결 정보가 주어질 때마다 해당 도시들이 연결되어있으면 도시에 해당되는 배열 값 즉, root값을 같게 만들어주면된다.

-여기서 배열의 인덱스는 도시를 의미하고 해당 인덱스의 배열 값은 도시의 root값을 의미한다.

- 두 도시가 배열값이 같다면 즉, 같은 root값을 갖는다면 해당 두 도시는 연결되어있으므로 여행가능한 도시이다.

#include <iostream>

using namespace std;

int find(int i, int*& arr)
{
	if (i!= arr[i])
	{
		return arr[i] = find(arr[i], arr);
	}
	else
	{
		return i;
	}
}
void merge(int a, int b, int*& arr)
{
	int A = find(a, arr);
	int B = find(b, arr);
	if (A!=B)
	{
		arr[B] = A;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	int* arr = new int[N];

	for (int i = 0; i < N; i++)
	{
		arr[i] = i;
	}

	int num;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> num;
			if (i!=j && num==1)
			{
				merge(i, j, arr);
			}
		}
	}
	bool check = true;
	int ci;
	for (int i = 0; i < M; i++)
	{
		cin >> num;
		if (i!=0)
		{
			if (find(num - 1, arr) != find(ci - 1, arr))
			{
				check = false;
			}
		}
		ci = num;
	}
	if (check)
	{
		cout << "YES";
	}
	else
	{
		cout << "NO";
	}
	return 0;
}