이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 63 번째 글 입니다.
목차
골드4 : 유니온 파인드 문제이다.
생각
이 문제의 핵심은 갈 수 있는지 없는지를 판단하는 것이다. 처음에 그래프라고 생각하고 접근하니, dfs를 수행할 때 depth가 너무 깊어져 터질 것 같아 다른 방법으로 진행했다.
갈 수 있는 지 없는 지를 판단하기 위해서 해당 문제에서 가장 중요한 조건은, 그래프의 방향성이 없다는 것이다. 방향성이 없기 때문에 일단 연결된 모든 노드들은 어떻게든 서로의 노드에 방문할 수 있다. 이 점이 핵심이다. 그렇기 때문에 우리는 특정 노드가 어디에 속해있는 지, 어느 그래프 묶음에 속해있는 지를 파악하는 것이 중요하다.
유니온 파인드
그렇다면 결국 어떠한 집합에 속해있는지를 판단해야 하는 문제로 바뀐다. 그 결과 이 문제는 유니온 파인드로 해결하는 것이 가장 간단해 보인다.
(1, 2)
이런식으로 연결되어 있다고 가정할 경우, 2의 노드의 조상을 1의 노드의 조상으로 업데이트 하는 방식을 사용했다.
Code
#include<iostream>
using namespace std;
int a[201];
int find(int x) {
if (x == a[x]) return x;
return a[x] = find(a[x]);
}
void Union(int x, int y) {
x = find(x);
y = find(y);
a[x] = y;
}
int main(void) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
a[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int input;
cin >> input;
if (input) {
Union(i, j);
}
}
}
int route[1000], par;
for (int i = 0; i < m; i++) {
cin >> route[i];
if (i == 0) {
par = find(route[i]);
}
else {
if (par != find(route[i])) {
cout << "NO";
return 0;
}
}
}
cout << "YES";
}