# 1976. 여행 가자

관련 알고리즘 : 유니온 파인드

 

문제 링크 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

---

해결 방법

 

동혁이가 여행 계획을 위해 이동해야 하는 최단 거리를 구하는 것이 아니라, 같은 곳을 여러 번 경유한다 해도 도시들을 순서에 따라 여행할 수 있을 지에 대한 여부를 구하는 것이기 때문에 유니온 파인드를 사용하였다.

같은 그래프에 여행 계획을 세운 도시들이 모두 포함되어 있다면 경유하여 갈 수 여행할 수 있다는 뜻이므로 yes를, 

도시들 중 하나라도 다른 그래프에 포함되어 있다면 경유하여 여행할 수 없다는 뜻이므로 no를 반환한다.

 

유니온 파인드에 대한 개념이 부족하여 관련 블로그

유니온 파인드(Union-Find)

를 참고하였다. 

 

---

C++ 코드

 

#include <iostream>

using namespace std;

int n; // 도시 수
int m; // 여행 계획에 속한 도시 수
int parent[201];

int find(int i) 
{
	if (parent[i] == i) // 공통 부모 합집합x 혹은 이 값 자체가 공통부모
    	return i;
	parent[i] = find(parent[i]); // 공통 부모 다시 찾기
    return parent[i];
}

void merge(int a, int b) 
{
	// 공통 부모 합집합 찾아내기
	a = find(a);
	b = find(b);

	if (a < b) 
    	parent[b] = a; // 공통 부모 합집합으로 묶어주기
	else 
    	parent[a] = b;
}

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

	cin >> n >> m;
    
	for (int i = 1; i <= n; i++) 
    {
    	parent[i] = i; // 처음 입력받을 시, 모든 
    }
    
	for (int i = 1; i <= n; i++) 
    {
		for (int j = 1; j <= n; j++) 
        {
			int tmp;
			cin >> tmp;
			if (tmp == 1) 
            	merge(i, j); // 인접한 도시들끼리 한 집합으로 합치기
		}
	}
    
	bool check = true;
	int root;
    
	cin >> root;
	int r = find(root);
    
	for (int i = 0; i < m - 1; i++) // m개 도시들이 같은 집합 내에 속해 있는지 확인
    {
		int t;
		cin >> t;
		if (r != find(t)) // 하나라도 같은 집합이 없을 때
        	check = false; // 여행 불가
	}
	if (check) 
    	cout << "YES\n";
	else 
    	cout << "NO\n";
        
	return 0;
}