[Java] LeetCode 1192 – Tarjan Algorithm으로 Critical Connections 찾기

0. 문제: 원문

1192. Critical Connections in a Network

There are `n` servers numbered from `0` to `n - 1` connected by undirected server-to-server `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between servers `ai` and `bi`. Any server can reach other servers directly or indirectly through the network.

A _critical connection_ is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

1. Tarjan Algorithm

이 문제는 어떠한 간선 하나를 제거했을때, 그래프가 끊어지는지를 구해야 하는 문제이다. 그러한 간선을 Critical Connection이라 부른다.

 

Brute Force한 방식으로 모든 간선을 끊어보고, 연결이 끊어졌는지를 확인하는 방법 또한 존재하나, 그 시간 복잡도는 매우 커질 것이다.

 

이번 글에서는 이런 문제를 풀기 위해 사용되는 DFS의 특별한 형태인 Tarjan Algorithm에 대해 이해한 바를 써보고자 한다.

 

이 알고리즘을 사용하면 단 한번의 DFS만으로 그래프 내의 모든 Critical Connection을 찾을 수 있다.

2. 문제의 핵심 아이디어

Critical Connection 의 본질은 다른말로 다음과 같다.

• 이 간선을 제거 했을 때, 두 정점을 연결 할 다른 경로가 있는가?
  • YES -> Safe
  • NO -> Critical Connection

이를 다르게 생각 해 본다면, 사이클에 포함된 간선은 Critical Connection이 될 수 없다.

 

Tarjan Algorithm은 이러한 점을 활용해 사이클의 존재 여부를 간접적으로 판별하며, Critical Connection을 구분해 낸다.

3. Tarjan Algorithm 핵심 개념

Tarjan Algorithm은 DFS를 수행하며 "자식의 정보"를 활용하여 "자신의 정보"를 업데이트 해야 한다.

 

그렇기 때문에, 다음 두가지 정보를 기록하며 DFS를 수행한다.

1. discovery time : DFS에서 해당 노드를 "처음" 방문한 시점
2. lowest discovery time reachable : 자신 or 자식 노드를 통해 되돌아 갈 수 있는 가장빠른 discovery time

즉, "언제 발견되었는가" 와 "이 노드가 어디까지 거슬러 올라갈 수 있는가" 이다.

 

위에서 언급한 1 을 disc 배열, 2를 low 배열이라 칭하겠다.

 

disc배열은 dfs를 수행하며 처음 방문한 시점을 기록하면 된다.

 

그렇다면 low 는 언제 갱신될까?

1. 노드를 처음 방문했을 때

disc[u] = low[u] = time++;

• 처음엔 자기 자신밖에 모르므로 low와 disc의 값이 같다.

2. 자식 노드가 DFS를 마치고 돌아왔을때

low[u] = Math.min(low[u], low[child]);

• 자식 노드가 조상으로 돌아 갈 수 있다면, 현재의 노드 또한 조상으로 돌아 갈 수 있다는 뜻이고, 현재 노드가 그 경로를 이용할 수 있다는 뜻이 된다.
• 즉, 자식 노드의 "경로"는, 부모 노드에게 전파된다.

3. 이미 방문한 조상으로 가는 간선을 발견했을 때

low[u] = Math.min(low[u], disc[child]);

• 이는 DFS 트리 기준으로 "사이클"이 존재함을 의미한다.

3.1 Critical Connection 판정 조건

DFS 트리에서 부모 노드 u 와 자식 노드 v를 잇는 간선 (u, v)에 대해 다음 조건을 확인한다.

low[v] > disc[u]

• 이 조건이 성립하는 상황은, 자식노드가, 부모 노드의 조상으로 되돌아 갈 수 있는 경로가 없음을 뜻한다.
• 따라서 간선 (u, v)는 Critical Connection이 되는 것이다.

4. 예시

다음과 같은 상황을 예로 들어보겠다.

• n = 4
• connections = [[0, 1], [1, 2], [2, 0], [1,3]]

탐색을 수행 하기 전 그래프의 상태이다.

 

0번 노드에서 시작하여 1번 노드를, 1번 노드에서 2번 노드를 탐색하고 해당 노드들의 disc, low 값을 채운다.

 

 

2번 노드는 이미 방문한 노드인 0번 노드의 disc 값과, 자신의 low 를 비교하여 자신의 low 를 업데이트 한다. 이러한 결과는 1번 노드까지 전파된다.

 

결과적으로, 이러한 3개의 노드는 사이클을 이루고 있고, Critical Connection이 될 수 없음이 증명되었다.

 

 

이제 1번 노드에서 다음 노드인 3번 노드를 탐색한다.

 

 

재귀 후 확인 결과, 3번 노드의 low = 3 이며, 1번 노드의 최초 발견 시간인 disc 보다 큰 것을 볼 수 있다.

 

그렇다면 이러한 간선 (1, 3) 이 끊긴다면 그래프가 끊어지는 Critical Connection이 되는 것이다.

5. 코드

class Solution {
    int[] disc;
    int[] low;
    boolean[] visited;
    List<List<Integer>> graph = new ArrayList<>();
    List<List<Integer>> ret = new ArrayList<>();
    int time = 0;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {

        disc = new int[n];
        low = new int[n];
        visited = new boolean[n];
        for(int i = 0; i<n; i++) graph.add(new ArrayList<>());

        for(List<Integer> conn : connections){
            int a = conn.get(0);
            int b = conn.get(1);
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        for(int i = 0; i<n; i++){
            if(!visited[i]){
                dfs(i, -1);
            }
        }

        return ret;

    }


    public void dfs(int node, int parent){

        visited[node] = true;
        disc[node] = low[node] = time++;

        for(int next: graph.get(node)){
            if(next == parent) continue;
            if(!visited[next]){

                dfs(next, node);
                low[node] = Math.min(low[node], low[next]);
                if(low[next] > disc[node]) ret.add(Arrays.asList(node, next));

            }else{
                low[node] = Math.min(disc[next], low[node]);
            }
        }
    }
}