백준 - 12784 인하니카 공하국(Java)

dfs 문제입니다.

 

진은 1번섬에 거주하고 있습니다.

괴도 루팡이 있을 만한 위치의 섬에서 1번 위치의 섬으로 올 수 없게 간선을 짜르는 문제입니다.

각 간선은 가중치가 있습니다.

 

각 섬들은 최소의 다리를 사용해 모두 연결되어 있다고 나와있습니다.

이 말을 다시 생각해보면 섬의 연결 관계는 최소 신장 트리(MST, Minimum Spanning Tree)라는 것을 알 수 있습니다.

또, 괴도 루팡은 다리가 하나인 섬에 있다고 나와있습니다.

이 말은 괴도 루팡은 리프 노드(Leaf Node)에 있다는 말입니다.

 

즉, 문제를 다시 해석하면 다음과 같습니다.

• 1번 노드와 모든 리프노드가 연결될 수 없게 간선을 짜른다. 단, 간선을 짜를 때의 가중치를 최소로 한다.

 

그러면, 가중치를 최소로 짜르는 방법은 어떻게 될까요?

 

문제에서 주어지는 예제 1번은 다음 그림과 같습니다.

 

최소로 짜르기 위해서는 다음 그림과 같이 짤라야 하기 때문에 가중치는 3입니다.

 

 

3, 4번을 짜르면 가중치는 5입니다.

하지만, 3,4번의 부모인 2번을 짜르게 되면 가중치는 1로 최소가 됩니다.

 

6, 7번을 짜르면 가중치는 3입니다.

6,7번의 부모인 5를 짜르게 되면 가중치는 4로 3보다 커지게 됩니다.

 

즉, 부모의 가중치와 자식 노드들의 가중치 최소 합을 비교하면 됩니다.

 

 

 

 

 

[구현 코드]

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

public class Main {
    private static List<List<Node>> graph;
    private static boolean[] visited;

    private static class Node{
        int e, d;

        public Node(int e, int d) {
            this.e = e;
            this.d = d;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        int testCase = Integer.parseInt(br.readLine());

        while (testCase-- >0){
            stz = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(stz.nextToken());
            int m = Integer.parseInt(stz.nextToken());

            graph = new ArrayList<>();
            for(int i=0; i<n+1; i++) graph.add(new ArrayList<>());

            for(int i=0; i<m; i++){
                stz = new StringTokenizer(br.readLine(), " ");

                int a = Integer.parseInt(stz.nextToken());
                int b = Integer.parseInt(stz.nextToken());
                int c = Integer.parseInt(stz.nextToken());

                graph.get(a).add(new Node(b, c));
                graph.get(b).add(new Node(a, c));
            }

            // 1번의 자식 노드들을 탐색
            visited = new boolean[n+1];
            visited[1] = true;
            int answer = 0;
            for(int i=0; i<graph.get(1).size(); i++){
                Node child = graph.get(1).get(i);
                answer += dfs(child.e, child.d);
            }

            bw.write(answer + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int dfs(int current, int midEdge){
        visited[current] = true;

        int childrenMinEdgeSum = 0; // 자식들 최소 간선들의 합
        boolean isLeaf = true; // 리프 노드인지 확인
        for(int i=0; i<graph.get(current).size(); i++){
            Node nn = graph.get(current).get(i);
            if(!visited[nn.e]) {
                isLeaf = false;
                childrenMinEdgeSum += dfs(nn.e, nn.d);
            }
        }

        // 리프이면 자기 자신이 최소 간선임
        if(isLeaf) childrenMinEdgeSum = midEdge;

        // 자식들의 최소의 '합'과 자신이 1번으로 가는 간선의 최소를 구해 반환함
        return Math.min(midEdge, childrenMinEdgeSum);
    }
}