[BOJ/백준] 31477 - 양갈래 구하기

 

31477번: 양갈래 구하기

---

N개의 방이 존재하고 N-1개의 각 방을 잇는 덩굴이 존재하며 각 방끼리 무조건 이동 가능

= 사이클이 생길 수 없는 구조

 

DFS를 통한 최소 두께를 갱신하여 합

---

---

• 제목

양갈래 구하기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

평화로운 양갈래의 마을에 위기가 닥쳐왔다! 덩굴에 독이 퍼져 양갈래가 있는 곳으로 옮겨지고 있다!

독은 양갈래의 방을 제외하고, 정확히 한 개의 덩굴로 연결된 방에서부터 옮겨진다.

모든 방의 쌍 사이에는 
1개 이상의 덩굴을 지나는 유일한 경로가 존재하며, 덩굴은 총 N-1개가 존재한다. 각 덩굴의 끝과 끝은 각각의 방에 강하게 연결되어 있어 양갈래의 방까지 독이 스며들지 않도록 덩굴을 잘라야 한다.

또한, 덩굴을 자르기 위해서는 덩굴의 두께 V의 힘이 든다. 양갈래의 방까지 독이 가지 않게 덩굴을 잘라야 양갈래를 구할 수 있다. 덩굴을 자르는 데에는 많은 힘이 들기에, 시현이는 가능한 한 적은 힘을 들이며 덩굴을 자르고 싶다.

시현이를 도와 덩굴을 자르기 위해 필요한 힘의 합의 최솟값을 구해주자!

---

• 입력

첫 번째 줄에는 방의 수 N이 주어진다. (2 ≤ N ≤ 100,000)

이후 N-1개의 줄에 세 정수 A, B, V가 사이에 공백을 두고 주어진다. (1 ≤ A, B ≤ N,1 ≤ V ≤ 1,000)

이는 A번 방과 B번 방을 연결하는 덩굴의 두께가 V라는 뜻이다.

양갈래가 묶인 방은 1로 주어진다.

---

• 출력

덩굴을 자르기 위해 필요한 힘의 합의 최솟값을 출력한다.

---

예제 입력1	예제 출력1
7 1 2 3 1 3 4 2 4 2 2 5 2 3 6 1 3 7 2	6

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N;
    static boolean[] visited;
    static ArrayList<int[]>[] edge;

    static int DFS(int curr){
        int sum = 0;
        for (int[] temp: edge[curr]) {
            int next = temp[0];
            int weight = temp[1];
            if(visited[next]) continue;
            visited[next] = true;
            sum += Math.min(weight, DFS(next));
        }
        return sum == 0 ? Integer.MAX_VALUE : sum;
    }

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        edge = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            edge[i] = new ArrayList();
        }
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            edge[A].add(new int[]{B, V});
            edge[B].add(new int[]{A, V});
        }
        visited[1] = true;
        System.out.println(DFS(1));
    }
}