BOJ - 여행가자(1976)

골드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";
}

Reference

• 백준(1976번) - 여행가자