(백준/c++) 1976번 - 여행 가자

1976번: 여행 가자 (acmicpc.net)

1976번: 여행 가자

1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 

2. 풀이: 문제에 나와 있는 거 문장을 보면 `같은 도시를 여러 번 방문하는 것도 가능하다.`라고 나와 있다. 여행 계획의 시작 지점을 시작으로 경로를 가기 위한 edge가 이어져 있다면 어떤 방법으로든 여행 계획을 한 번씩 들려서 목적지까지 도달할 수 있다. 밑에는 백준 문제에 예시를 그림으로 표현하고 배열의 인덱스에 맞는 value 값을 표현한 것이다. 

이처럼 여행 계획의 경로를 가리키는 value가 모두 같은 값일 때 목적을 달성할 수 있고 value가 하나라도 다르면 목적을 달성할 수 없다.

3. 구현

	#include <iostream>
	#include <algorithm>
	#include <vector>
	using namespace std;
	int getParent(vector<int>& parent, int a)
	{
	if (parent[a] == a) return a;
	return parent[a] = getParent(parent, parent[a]);
	}
	void Union(vector<int>& parent, int a, int b)
	{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
	}
	int Find(vector<int>& parent, int a, int b)
	{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1;
	else return 0;
	}
	int main()
	{
	int n, m;
	cin >> n >> m;
	vector<int> arr;
	arr.resize(n + 1);
	for (int i = 1; i <= n; ++i)
	{
	arr[i] = i;
	}
	for (int i = 1; i <= n; ++i)
	{
	for (int j = 1; j <= n; ++j)
	{
	int a;
	cin >> a;
	if (a)
	{
	Union(arr, i, j);
	}
	}
	}
	vector<int> plan;
	for (int i = 1; i <= m; ++i)
	{
	int a; cin >> a;
	plan.push_back(a);
	}
	for (int i = 0; i < m-1; ++i)
	{
	if (arr[plan[i]] != arr[plan[i + 1]])
	{
	cout << "NO";
	return 0;
	}
	}
	cout << "YES";
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub