[BOJ] 백준 12784번 인하니카 공화국 (Java)

#12784번 인하니카 공화국

난이도 : 골드 3

유형 : 트리 / DFS

12784번: 인하니카 공화국

▸ 문제

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

 

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

▸ 입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 섬의 수 N(1 ≤ N ≤ 1,000)과 다리의 수 M이 주어진다.

다음으로 M개의 줄에는 각 다리를 통해 이어진 두 섬의 번호와 다리를 파괴하기 위한 다이너마이트의 수 D(1 ≤ D ≤ 20)가 주어진다.

▸ 출력

각 테스트 케이스마다 필요한 최소 다이너마이트의 개수를 출력한다.

 

문제 풀이  

트리 DFS 문제로 후위 순회로 탐색해주면서 풀이를 해주면 된다.

 

다리가 1개인 섬들은 리프노드밖에 없다. 최소로 다리를 끊을 방법을 찾아보면  최소 다이너마이트의 갯수는 리프 노드의 갯수와 그와 연결되어 있는 부모 노드들의 가중치와 비교하면 된다. 

• 자식이 가지고 있는 모든 가중치를 더하여 루트의 가중치보다 작으면 해당 다리를 폭파시키고
• 반대로 루트의 가중치가 더 작다면 루트를 폭파시키는 방법을 택한다.
• 그렇게 필요한 모든 다이너마이트의 갯수를 합쳐서 출력해주면 된다. 

 

폭탄 설치 과정

 

설계

1. 트리 간선 데이터를 양방향으로 입력받는다.
2. DFS탐색으로 1번을 루트로 탐색을 시작한다.
   1. 각 계층에 필요한 다이너마이트의 갯수를 구한다.  ret += dfs(nxt.to, here, nxt.w);
   2. 현재 루트노드를 폭파시키는데 필요한 갯수(bomb)와 비교하여 더 작은 값을 가져온다. Math.min(ret, bomb);
3. 1번까지 모두 탐색이 끝나면 최소의 갯수를 구하여 출력한다.

 

풀이 코드 

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

public class Main {
	static class Node{
		int to;
		int w;
		
		public Node(int to, int w) {
			this.to = to;
			this.w = w;
		}
	}
	static int n,m, INF = 987654321;
	static List<Node>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		while(t-->0) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			
			list = new ArrayList[n+1];
			for(int i=1; i<n+1; i++) {
				list[i] = new ArrayList<>();	
			}
			
			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 w = Integer.parseInt(st.nextToken());
				
				list[a].add(new Node(b,w));
				list[b].add(new Node(a,w));
			}
			int res = dfs(1, -1, INF);
			
			sb.append((res==INF? 0:res) +"\n");
		}
		System.out.println(sb.toString());
	}
	
	static int dfs(int here, int pa, int bomb) {
		int ret=0;
		for(Node nxt : list[here]) {
			if(pa != nxt.to) {
				ret += dfs(nxt.to, here, nxt.w);
			}
		}
		if(ret == 0) { // leaf 
			ret = bomb;
		}
		return Math.min(ret, bomb);
	}
}