[백준 1976번 / C++ / Find&Union] 여행 가자

Find&Union을 활용한 문제이다. 

 

#접근방법 

 

union 벡터를 생성하여 각 인덱스의 부모 노드를 자신의 인덱스 값으로 초기화 한다.

 

map 배열에 i에서 j로 가는 경로가 있으면서 현재 i와 j의 부모노드가 다르다면 Union함수를 호출한다. 

 

Union 함수에서는 자신의 부모노드를 찾으러 Find라는 함수를 호출한다. 

 

Find 함수에서는 매개변수로 받은 값을 가지고 부모 노드를 찾으러 올라간다. 

만약 자기 자신이 부모노드라면 해당 부모노드의 값을 반환한다. 

 

이후 다시 Union함수에 돌아오면 i와 j의 부모노드를 알 수 있다. 

만약 i가 j보다 작다면 j의 부모노드를 a로 설정한다. 

반대로 i가 j보다 크거나 같다면 i의 부모노드를 j로 설정한다. 

 

출력은 현재 경로의 첫번째 위치의 부모 노드의값과 이후 가야할 경로의 부모 노드의 값이

일치해야 YES라는 결과가 나온다. 

 

즉, 부모노드가 같아야 다 둘러볼 수 있다는 뜻이다. 

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std; 
int map[201][201];  
vector <int> uni; 

int Find(int parent) {
	if (parent == uni[parent])return parent; 
	uni[parent] = Find(uni[parent]); 
	return uni[parent]; 
}

void Union(int a, int b) {
	a = Find(a); 
	b = Find(b); 
	if (a < b)uni[b] = a;
	else uni[a] = b; 
}

int main() {
	int n; cin >> n;
	int m; cin >> m; 
	uni.resize(n + 1, 0); 
	for (int i = 1; i <= n; i++) {
		uni[i] = i; 
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j]; 
		}
	}
	
	vector <int> order; 
	for (int i = 0; i < m; i++) {
		int x; cin >> x; 
		order.push_back(x); 
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (map[i][j] && uni[i] != uni[j])Union(i, j); 
		}
	}

	bool check = true; 
	int cur = uni[order[0]]; 
	for (int i = 1; i < m; i++) {
		if (cur == uni[order[i]]) {
			if (i == m)check = true; 
		}
		else {
			check = false; 
			break; 
		}
	}


	if (check)cout << "YES\n";
	else cout << "NO\n"; 

}

1976번: 여행 가자