11400번: 단절선 - Baekjoon Online Judge

단절선 알고리즘은 완전 그래프에서 어떤 간선을 제거하였을 때, 그래프가 두 개 이상의 영역으로 나누어지는지 알아내기 위한 알고리즘이다. 문제를 단절선 알고리즘으로 규정짓기 위해서는 몇 가지 조건이 주어져야 한다. 

첫째 완전 그래프여야 한다. 완전 그래프는 모든 노드가 간선으로 연결되어 어느 한 노드도 빼놓지 않고 연결이 되어 있는 경우를 의미한다.

완전 그래프의 정의

https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84_%EA%B7%B8%EB%9E%98%ED%94%84

둘째 한번에 하나의 간선만 끊을 수 있다. 동시에 여러 간선을 끊는다던가 한번 끊어진 간선은 계속 끊어진 상태로 있다던가 하는게 아니라 연결되어 있는 상태에서 한번에 하나씩 끊어져야 한다.

단절선 알고리즘은 일단 모든 노드와 간선의 연결 정보를 입력받고 그에 따른 연결관계를 반영한 그래프 구조를 그리는데서 풀이가 시작된다. 그래프류 문제를 많이 풀어본 사람이면 그래프 구조를 구성하는 자신만의 방식이 있겠지만, 일반적으로 노드 수 만큼 Array를 선언하고 Array에 하나씩 List 객체를 입력하는 형식으로 구현하는 경우가 많은 듯하다. 노드마다 연결되어 있는 간선의 숫자가 다 다르기 때문에 이 방법이 제일 효율적일 것으로 생각된다. 구조가 완성이 되면 한 점을 잡아서 그 점을 시작점으로 하여 깊이 우선 탐색(DFS: Depth First Search)을 통해 방문하지 않는 노드마다 하나씩 index를 부여한다. 재귀함수를 이용하여 방문하지 않은 노드가 나올 때마다 새로운 함수를 실행하여 노드에 index를 부여하는 방식으로 구현한다. 문제에서는 완전 그래프라는 조건이 주어지기 때문에 어떤 점을 선택하여 탐색을 시작하든 모든 노드들은 자신만의 index를 갖게 된다. 마지막까지 탐색이 완료되면 더이상 갈곳을 잃은 함수들은 하나씩 종료되는데 이 과정에서 노드 간 간선이 단절선인지 판단하게 된다. 함수는 종료되면서 하나의 Integer value를 return 하게 된다. 이 값은 자기 자신이 가진 index 값과 자신이 연결된 노드들의 index 값들과 비교하여 가장 작은 값이 되는데 이 때 자신의 부모 노드는 비교대상에서 제외된다. 부모 노드와 index를 비교하는 것으로 간선이 단절선인지 판단하기 때문이다. 그리고 이렇게 return된 값과 부모노드의 index를 비교하여 만일 부모노드의 index보다 return 된 값이 더 크다면 그 선은 단절선이 된다. 깊이 탐색에서 후위 탐색된 노드가 부모보다 먼저 등장하는 노드와 연결이 되어 있다는 것은 부모 노드와 연결이 끊어지게 되더라도 그 외의 연결고리가 있다는 것이 증명하는 것으로써 그 간선이 단절선이 아니라는 결론을 얻을 수 있기 때문에 이와같은 논리가 성립하게 된다. 이는 return된 값은 단순히 1회 계산에 사용되고 끝나는 것이 아니라 적어도 그 index보다 낮거나 같은 숫자의 index를 가진 노드가 등장하기 까지 계속 사용된다는 것을 의미하기도 한다. 자신보다 하위에 있는 노드가 자기보다 먼저 등장한 노드와 연결이 되어 있다면 그 간선이 단절된다고 해도 하위 영역에서 분명 다른 앞선 노드와 연결되어 있다는 사실을 의미하기 때문이다. 만일 단절선이라면 노드가 return 할 수 있는 index는 부모와의 연결을 제외한 상황에서 얻을 수 있는 가장 작은 index 값이기 때문에 자기 자신의 index가 될 것이고, 이 값은 부모가 가진 index 값보다 크게 되어 단절선이 되는 것이다.

참고문제

11400번: 단절선 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    private static BufferedReader br;
    private static BufferedWriter bw;
    private static StringTokenizer st;
    private static int[] in;
    private static int cnt;
    private static ArrayList<Integer>[] con;
    private static ArrayList<int[]> ans;
 
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        st = new StringTokenizer(br.readLine().trim());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        in = new int[N + 1];
        ans = new ArrayList<int[]>();
 
        con = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            con[i] = new ArrayList<Integer>();
        }
 
        for (int m = 1; m <= M; m++) {
            st = new StringTokenizer(br.readLine().trim());
 
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            con[a].add(b);
            con[b].add(a);
        }
        dfs(1, 0);
        Collections.sort(ans, new Comparator<int[]>() {
            @Override
            public int compare(int[] o0, int[] o1) {
                if (o0[0] == o1[0])
                    return o0[1] - o1[1];
                return o0[0] - o1[0];
            }
        });
        bw.write(ans.size() + "\n");
        for (int[] a : ans) {
            bw.write(a[0] + " " + a[1] + "\n");
        }
        bw.flush();
        bw.close();
    }
 
    public static int dfs(int a, int p) {
        in[a] = ++cnt;
        int ret = in[a];
 
        for (Integer i : con[a]) {
            if (i == p)
                continue;
            if (in[i] == 0) {
                int l = dfs(i, a);
                if (l > in[a]) {
                    if (i < a)
                        ans.add(new int[] { i, a });
                    else
                        ans.add(new int[] { a, i });
                }
                ret = Math.min(ret, l);
            } else {
                ret = Math.min(ret, in[i]);
            }
        }
        return ret;
    }
}