[백준 1976] 여행가자_union_find(C++)

유니온 파인드란?

• 그래프 알고리즘의 일종이다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은집합에 있는지 확인하는 알고리즘이다. 또한 여러 노드가 존재할 때, 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 있는지의 여부를 판별하는 알고리즘.

1. find 연산 노드 x가 어느 집합에 포함되어 있는지 찾는 연산
2. Union 연산 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

• 서로소 집합(disjoint Set)그리고 병합 찾기 집합(merge find set) 이라 고도 불리며 여러 서로소 집합의 정보를 저장하고 있는 자료구조

참고사이트 : https://brenden.tistory.com/33

---

[문제]

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

• 여행 계획에 속한 도시들의 수가 M개 주어진다(전체 도시는 N개)
• 임의의 도시들이 연결되어 있는지의 여부가 주어진다
• 맨 마지막 줄에는 동혁이의 실제 여행계획이 주어진다
• 이것이 가능한지를 출력하면 된다

 

[문제풀이]

예제를 예시로 들어보자.

일단 모든 도시들이 자기자신을 가리키고 있도록 만든다. 즉, 자기 자신만을 집합의 원소로 가지고 있는것이다. 윗줄은 노드, 아랫줄을 부모노드를 뜻한다.

NODE	1	2	3	4	5
PARENT	1	2	3	4	5

 

동혁이가 갈 도시는 1,2,3인데 이 도시들이 어떻게 연결되어 있는지 아래의 표로 주어지게 된다.

	1	2	3
1	0	1	0
2	1	0	1
3	0	1	0

2중FOR문을 돌면서 관계가 1인 도시들은 UNION연산처리 해준다

1. 도시 1과 2를 union_xy(1,2) 을 하면
2. 도시 1의 부모노드인 1을 x에 저장. x = 1
3. 도시 2의 부모노드인 2를 y에 저장. y = 2
4. 만약 둘의 부모노드가 같지 않고 y가 더 크므로 parent[y] = x하여 y의 부모는 x가 되어버린다 parent[2] = 1;

유니온 연산으로 표가 바뀐다

 

다음 연결되어 있는 도시도 보면, 2와 1인데

1. union(2,1)을 하면 x = 1, y = 1 ⇒ 같으므로 연산의 의미가 없다 return!

 

그다음은 2와 3이다. 얘네도 살펴보면

1. union(2,3) ⇒ x = 1, y = 3
2. y > x 이므로 parent[3] = 1;

 

마지막으로

1. union(3,2) ⇒ x = 1, y = 1 ⇒ 같으므로 return!

이제 표가 다 셋팅되었으니 동혁이가 가고자하는 여행루트가 가능한지 확인해주면된다

path벡터에 1→2→3 여행루트를 저장해준다음

차례대로 부모노드가 같은지만 확인해주면된다.

만약 하나라도 다르다면 불가능하다는 것이므로(check == false) NO를 출력하게된다.

 

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

vector<int> parent;//부모노드를 받을 벡터
vector<int> path;

int arr[201][201];

//find 연산
int find(int node){
	if(node == parent[node]) return node; //자기자신이 부모노드라면 그 노드 반환
	else {
		int other = find(parent[node]);//node의 부모노드를 찾아서 other에 저장
		parent[node] = other; //노드를 부모노드로 바꿔줌
		return other;
	}
	return parent[node];
}

///유니온 연산
void union_xy(int x, int y){
	x = find(x);//find연산으로 각각의 root를 찾아준 후
	y = find(y);
	
	if(x == y) return;
	
	if(x < y) parent[y] = x;
	else parent[x] = y;
}
	
int main() {
	int N,M;
	cin >> N >> M;
	
	parent = vector<int> (N+1,0);
	path = vector<int> (M+1,0);
	
	for(int i = 1; i <= N; i++)
		parent[i] = i; //일단 부모노드에 자기자신 저장
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> arr[i][j];
			
			if(arr[i][j]== 1) union_xy(i,j);
		}
	}
	
	for(int i = 1; i <= M; i++) cin >> path[i];
	
	bool check = true;
	for(int i = 1; i < M; i++){
		if(find(path[i]) != find(path[i+1])){
			check = false;
			break;
		}
	}
	
	if(check) cout << "YES\n";
	else cout << "NO\n";
	
	return 0;
}