백준 12784 인하니카 공화국

이번주 미칠듯이 바빠서 몇일간 포스팅을 못했다 ㅠㅠ (사실 몇번이나 했다고)

 

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

12784번: 인하니카 공화국

 

문제의 핵심은 "한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다." 내용이다. 즉 1번을 루트로 가지는 트리라는 점 간선수는 당연히 N-1개

 

그래프형식으로 입력 받은 데이터들을 기반으로

루트인 1번부터 dfs를 돌리면서

자식들의 합과 자신의 값을 비교하면서 최소값을 갱신한다.

1번 노드를 예외처리해야되는데 1번노드는 값을 INF로 임의로 설정하여 합이 리턴될수있게해준다.

 

 

ps) 987654321를 98654321로 쓰는 헛짓거리를 해서 10번도 더틀렸다... INF =987654321로 변수를 만들어서 하자

 

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

public class Main {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}

	static int inorder(int idx, int val) {
		int sum = 0;
		boolean kk = false;
		v[idx] = true;
		for (int[] t : graph[idx]) {
			if (!v[t[0]]) {

				kk = true;
				sum += inorder(t[0], t[1]);
			}
		}
		if (kk == false)
			return val;
		else
			return Math.min(sum, val);
	}

	static boolean[] v;
	static ArrayList<int[]> graph[];

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();

		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			int M = sc.nextInt();

			graph = new ArrayList[N + 1];
			for (int i = 1; i <= N; i++) {
				graph[i] = new ArrayList<int[]>();
			}
			v = new boolean[N + 1];
			for (int i = 0; i < M; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int z = sc.nextInt();
				graph[x].add(new int[] { y, z });
				graph[y].add(new int[] { x, z });

			}
			
			int INF = 987654321;
			int answer = inorder(1, INF);
			if (answer == INF)
				answer = 0;
			System.out.println(answer);
		}
	}

}