백준 12784번: 인하니카 공화국

문제 설명

• https://www.acmicpc.net/problem/12784
• 모든 리프노드로부터 1번노드로 접근할 수 있는 길을 차단해야 합니다.
  이때 차단비용이 최소가 되도록 길을 차단하려면 얼마의 비용이 소모되는지 구하는 문제입니다.

접근법

• 중간 노드를 기준으로 위로 가는 길을 끊는게 이득일지 아니면 아래의 길을 모두 끊어야 할지를 선택해야 합니다.
  
  • d2 +d3 와 d1을 비교해 더 작은 값을 선택하면 됩니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			Map<Integer,List<Node>> graph = new HashMap<Integer,List<Node>>();
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				makeVertex(a,b,c,graph);
				makeVertex(b,a,c,graph);
			}
			Node root = new Node(1,Integer.MAX_VALUE);
			boolean[] v = new boolean[N+1];
			Node e = DFS(root,graph,v);
			System.out.println(e.dp);
		}		
	}
	public static void makeVertex(int from, int to, int dist, Map<Integer,List<Node>> graph) {
		if(graph.containsKey(from)) {
			graph.get(from).add(new Node(to,dist));
		}else {
			List<Node> temp = new ArrayList<Node>();
			temp.add(new Node(to,dist));
			graph.put(from, temp);
		}
	}
	public static Node DFS(Node now, Map<Integer,List<Node>> graph, boolean[] v) {
		v[now.num] = true;
		if(graph.containsKey(now.num)) {			
			for (Node next : graph.get(now.num)) {
				if(v[next.num]) continue;
				v[next.num] = true;
				Node c = DFS(next,graph,v);
				now.child.add(c);
				now.dp += c.dp;
			}
			if(now.dp != 0) {
				now.dp = Math.min(now.dp,now.distToParent);			
			}else { // 리프 노드
				now.dp = now.distToParent;
			}
		}
		return now;
	}
	
	public static class Node{
		int num;
		int distToParent;
		int dp;
		List<Node> child = new ArrayList<Node>();
		public Node(int to, int d) {
			super();
			this.num = to;
			this.distToParent = d;
		}
		@Override
		public String toString() {
			return "Info [num=" + num + ", d=" + distToParent + ", distSum=" + dp + ", child=" + child + "]";
		}
	}
}