[백준oj] 1976번 여행가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

---

이 문제는 그래프의 합집합을 이용하여 문제를 풀었다.

이어져 있는 도시들중 가장 낮은 도시로 부모를 설정을 해둔뒤, 마지막에 M개의 도시들의 부모 도시가 같으면 YES, 같지 않다면 NO를 출력하면된다.

 

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int arr[200][200] = { 0 };
vector<int> v;
int parent[200];

int getParent(int a) {
	if (a == parent[a]) {
		return a;
	}
	else {
		return parent[a]=getParent(parent[a]);
	}
}

void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a == b) return;
	else {
		if (a < b) {
			parent[b] = a;
		}
		else {
			parent[a] = b;
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
    
    //도시들 연결 관계 입력과 동시에 연결
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				unionParent(i, j);
			}
		}
	}
    
    //여행할 도시들 저장
	v.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> v[i];
	}
    
	bool flag = true;//부모가 같은지를 저장하는 변수
	for (int i = 0; i < m - 1; i++) {
    	//연결된 도시중 가장 작은 도시가 같지않으면 flag=false후 break
		if (parent[v[i] - 1] != parent[v[i + 1] - 1]) {
			flag = false;
			break;
		}
	}
	if (flag) cout << "YES";
	else cout << "NO";
	
	return 0;
}