기술면접 알고리즘 [Graph] : 유니온 파인드 / 사이클 찾기 (Union-Find / Cycle Detection)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

유니온 파인드 / 사이클 찾기 (Union-Find / Cycle Detection)

유니온 파인드는, disjoint set 들을 합쳐서 각 vertex 들이 같은 집합인지 아닌지 판별하는데 사용되는 알고리즘이다.

parent 배열에 각 vertex 의 조상(root node) 의 정보를 저장하고, find, union 등의 함수를 이용해 부모 노드를 탐색하고 집합을 합친다. 

find 함수를 구현할 때, 재귀적으로 경로 탐색 도중 만난 vertex 들이 부모 노드를 가리키도록 만듦으로써 path compression 을 할 수 있다.

Cycle Detection 의 원리는 다음과 같다 : 새로운 edge 에 대해, 시작 지점과 도착 지점의 vertex 가 이미 같은 집합에 있다면, 해당 그래프는 사이클이 존재한다.

유향 그래프에서는 사이클 검출이 조금 다른데, 탐색중인 노드와 방문이 완료된 노드로 종류를 분류하여, DFS 로 탐색 중 탐색중인 노드를 발견하게 되면 사이클이 있다고 판단한다. 자세한 사항은 이 글이나 이 글을 참조하자.

#include <iostream>
#include <list>
#include <queue>

using namespace std;

class Graph {
  
 int N;
 list<int>* g;
  
public:
  
  Graph(int n) : N(n) {
      g = new list<int>[n];
  }
  
  void addEdge(int i, int j) {
      g[i].push_back(j);
      //g[j].push_back(i);
  }
  
  void BFS(int s);
  
  ~Graph() { delete g; }
};

void Graph::BFS(int s) {
    queue<int> q;
    bool visit[N];
    for (auto b : visit) b = false;
    
    q.push(s);
    
    int cur;
    
    while (!q.empty()) {
        
        cur = q.front();
        visit[cur] = true;
        q.pop();
        
        cout << cur;
        for (int next : g[cur]) {
            if (!visit[next]) {
                q.push(next);
            }
        }
    }
    cout << endl;
}

int main() {
     // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    cout << "Following is Breadth First Traversal "
         << "(starting from vertex 2) \n";
    g.BFS(2);

    return 0;
}