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

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

12784번: 인하니카 공화국

문제

인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다. 1번섬에서 살고 있는 진은 어느 날 위험한 소문을 듣게 되었다. 1번섬을 제외한 다리가 하나밖에 없는 어느 섬에서 유명한 연쇄 살인마 괴도‘루팡’이 자신의 목숨을 노리고 있다는 소문이었다. 너무 불안한 나머지 진은 몇 개의 다리를 폭파하여, 루팡이 있을 가능성이 있는 모든 섬에서 자신의 섬으로의 모든 경로를 차단하려고 한다. 하지만 각 다리를 폭파하려면 다리의 크기에 따라 다이너마이트의 개수가 다르다. 다이너마이트는 매우 비싸기 때문에 진은 사용하는 다이너마이트의 개수를 최소화하고 싶어 한다. 각 섬을 연결하는 다리를 폭파하기 위한 다이너마이트의 개수가 주어졌을 때, 진을 도와 필요한 최소 다이너마이트의 개수를 구하라.

예를 들어, 위의 그림과 같이 섬과 다리를 폭파하기 위한 다이너마이트의 수가 주어졌을 때, 빨간색 다리를 폭파하면 다이너마이트의 개수를 최소화하면서 루팡으로부터 안전할 수 있다.

 

유형 : DFS + 트리에서 DP

 

접근 방식

• 문제를 통해 알수 있듯이 입력은 트리이다. 그리고 1번을 기준으로 하므로 1번 정점이 루트 노드이다.
• 트리에서 연결된 간선이 1개뿐인 정점은 ? : 리프 노드
  • 즉 위 문제는 리프 노드에서의 합산 값들과 위로 올라가면서의 경로 값을 비교하면 되는 문제이다.
• 예시를 들어 설명하자면
  • (1 - 2) VS (2 - 3) + (2 - 4)
  • (1 - 5) VS (5 - 6) + (5 - 7)
• 위의 값들을 비교해서 합산하면 되는 문제이다.

전체 코드

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

public class Main {

    static int t,n,m;

    static ArrayList<Node>[] graph;

    static boolean[] v;

    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        t = Integer.parseInt(st.nextToken());

        for(int a = 1; a <= t ; a++){
            st = new StringTokenizer(br.readLine()," ");

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            graph = new ArrayList[n+1];
            v = new boolean[n+1];
            dp = new int[n+1];

            for(int i=1 ;i<=n;i++){
                graph[i] = new ArrayList<>();
            }


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

                int v1= Integer.parseInt(st.nextToken());
                int v2= Integer.parseInt(st.nextToken());
                int c= Integer.parseInt(st.nextToken());

                graph[v1].add(new Node(v2,c));
                graph[v2].add(new Node(v1,c));
            }

            sb.append(dfs(1,0)+"\n");
        }

        System.out.print(sb);
        br.close();
    }

    static int dfs(int cur,int p){

        v[cur] = true;

        if(graph[cur].size() == 1 && graph[cur].get(0).v == p){
            return dp[cur] = graph[cur].get(0).c; // 리프노드라면 해당 값 바로 반환
        }

        for(Node next : graph[cur]){

            int tmp = 0;

            if(!v[next.v]){
                tmp = dfs(next.v,cur); // 자식 노드에서 최솟값
            }

            dp[cur] += Math.min(tmp,next.c); // 부모에서 자식으로 가는 값과 아래에서부터 올라온 값 비교
        }

        return dp[cur];
    }
}
class Node{
    int v;
    int c;

    Node(int v,int c){
        this.v = v;
        this.c = c;
    }
}