(백준 1976번 여행 가자 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 2

(노느라) 바쁘다는 핑계로 공부를 소홀히 하는 것 같아 마음이 불편하다.

이제는 진짜 매일 1백준 해야겠다!!!

 

백준 1976번

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

 

이 문제는 Union Find 라고 해서 봤는데 처음에는 뭔 소리인가 했다. dfs로 풀어야 하나 생각하고 있었는데!

Union Find로 아이디어를 틀었다.

 

이디야에서 샤인히비스커스를 마시면서 깨달은 사실 : 

사실 어떤 도시를 몇 번 가는지는 중요하지 않다! 연결된 도시는 무조건 방문이 가능하다. 

 

이 말인 즉, 여행을 가고지 하는 도시들이 하나의 connected graph의 node들이기만 하면 된다는 의미!

그리고 하나의 connected graph에 속하는지 아닌지는 root node가 동일한지 아닌지만 확인하면 된다!

 

graph 중에서 가장 작은 숫자가 root가 되도록 코드를 작성해보자.

 

// 백준 1976번
#include <iostream>
using namespace std;

constexpr int MAX_N = 200 + 1;
int p[MAX_N];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void _union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[b] = a;
	return;
}

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

	int n, m; cin >> n >> m;
	fill_n(p, n, -1);
	
	int temp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			if (temp == 1 && j > i) _union(i, j);
		}
	}

	int root;
	cin >> temp; temp--;
	root = find(temp);
	
	for (int i = 0; i < m-1; i++) {
		cin >> temp; temp--;
		if (root != find(temp)) {
			cout << "NO"; return 0;
		}
	}
	
	cout << "YES"; return 0;

}

 

반례(https://www.acmicpc.net/board/view/114412)

5
5
0 1 0 0 0
1 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 1 0 1 0
3 5 4 2 1

 

그리고 내가 만든 반례 - 99%에서 틀린다면 시도해볼만 함!

2
2
0 0
0 0
1 2