[백준 11400] 단절선 / 자바 / dfs **

#문제         

레벨: P4
알고리즘: dfs
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

가장 쉬운 방법은 모든 단절선을 끊어보고 dfs 여러번을 통해 트리의 개수가 2개이상인지 세어보는 것이다. 그러나 입력제한을 보면 시간초과가 날 것을 직감할 수 있다.

문제의 해결법은 노드를 처음 발견했을 때의 순서와 만남의 가중치를 이용해 푸는 것이다. 처음 방문한 노드라면 처음 발견했을 때의 변수와 만남의 가중치에 발견한 순서를 부여해준다. 만약 처음 방문한 게 아니라면  

1를 시작으로 탐색했을 때 1 -> 4 -> 5  -> 6(1에 의해) -> 7 -> 2 -> 3이렇게 정점을 탐색하는 것이다. 근데 우리가 중요한 건 간선을 탐색하는 거다. 간선을 탐색하는 건 dfs를 통해 직접 연결된 노드를 방문하는 것이 아니라 이미 방문한 흔적이 있는 노드라면 그 노드의 값을 참조하는 게 간선을 따라 탐색하는 거다. 보면 우리 7개의 정점을 방문했지만 8개의 간선을 탐색했다고 치는 거다. 했다고 치는 방식은 다음 노드를 뽑기는 하되 그 다음 노드로 dfs를 넘기는 게 아니라 다른 일을 처리하는 것이다.  

 

왼쪽 숫자는 처음 발견한 순서값이고 오른쪽 숫자는 만남의 가중치이다. 순서대로 탐색하게 된다면 1 -> 5 - > 4 순서대로 탐색할 것이다. 

이제 4 ->1를 가려고 하는데 1이 이미 방문한 노드이다. 그래서 1이 처음 발견했을 때의 순서와 4의 가중치를 비교한다. 1과 3중 작은 값은 1이니 노드 4의 가중치를 1로 바꿔준 후 리턴해준다. 

1-> 5 -> 4의 탐색이 끝났다. 탐색이 끝났으니 남은 dfs 코드를 처리하기 위해 다시 이전 노드들로 복귀하여 처리해줄 것들을 처리해준다. 노드4의 이전 노드인 5로 돌아가 4가 리턴해준 노드4의 가중치와 자신의 가중치를 비교해준다.  만약 리턴해준 노드4의 가중치가 더 컸다면 절단선 배열에 추가했을 것이다. 그러나 자신의 가중치가 더 크니 그냥 넘어간다. 리턴받은 노드 4의 가중치와 자신의 가중치 중 작은 값을 자신의 가중치로 설정해준다. 노드 5의 가중치는 1이 되고 리턴해준다. 

다시 5의 이전 노드인 1로 돌아가 노드1의 가중치와 노드 5의 가중치를 비교한다. 1과 1은 똑같으므로  절단선 배열에 추가하지 않는다. 1과 1 중 작은 값인 1로 노드1의 가중치는 1이 된다. 이렇게 노드1에서 시작한  첫 번째 for문이 끝났다 두 번째 for 문은 노드6으로 간다.

노드 6으로 간 후 끝까지 탐색하게 되면 6 -> 7 -> 2 -> 3 순서대로 탐색하게 되면서 처음발견한 순서와 가중치를 부여할 것이다.

 

 자 이제 3에서 7로 가려했더니 7이 이미 방문한 노드여서 1-5-4 싸이클을 만났을 때처럼 가중치가 바뀌는 과정이 일어난다. 이렇게 7까지 복귀를 했다. 이제 6으로 복귀할 차례이다. 

어머.  노드6으로 복귀 하고 노드 7 dfs에서 리턴해준 노드 7의 가중치인 5가 노드6의 가중치인 4보다 크다. 드디어 절단선을 찾았다. 절단선 배열에  (6-7)을 추가해준다. 가중치 5와 4중 4가 더 작으니 노드6의 가중치는 똑같이 4이다. 

 

노드 1로 복귀하고 나서 노드6 dfs에서 리턴해준 노드 6의 가중치와 비교하면 4와 1이므로 (1-6)도 절단선 배열에 추가해준다.

 

이렇게 dfs가 모두 끝나고 배열에  (6-7),  (1-6)  두 개의 답이 도출됐다.

 

---

#풀이 코드      

import java.io.*;
import java.util.*;

public class Main {
    static int V, E;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] discovered;
    static ArrayList<int[]> bridges;
    static int counter = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        discovered = new int[V + 1];
        bridges = new ArrayList<>();

        dfs(1, 0);

        Collections.sort(bridges, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        System.out.println(bridges.size());
        for (int[] bridge : bridges) {
            System.out.println(bridge[0] + " " + bridge[1]);
        }
    }

    static int dfs(int node, int parent) {
        discovered[node] = ++counter;
        int ret = discovered[node];

        for (int next : graph.get(node)) {
            if (next == parent) continue;
            if (discovered[next] == 0) {
                int subtree = dfs(next, node);
                if (subtree > discovered[node]) {
                    bridges.add(new int[]{Math.min(node, next), Math.max(node, next)});
                }
                ret = Math.min(ret, subtree);
            } else {
                ret = Math.min(ret, discovered[next]);
            }
        }

        return ret;
    }
}