[BOJ_20924] 트리의 기둥과 가지

설명

---

생각과 달리 예외 상황에서의 처리가 부족해서 시간이 오래걸렸던 문제다. DFS를 간단히 돌면서 카운트하면 될 줄 알았지만 루트가 기가노드일때의 상황을 고려를 충분히 하지 않아서 시간이 걸렸다.(R == idx && list[idx].size() >= 2 일때) 그리고, 기가 노드 속으로 들어 갔을때 거기서 부터 2개 이상의 가지로 나뉠때 카운트를 충분히 고려하지 않아서 처음에 헷갈렸던 문제다. (cnt -= 부분)

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Node {
        int node;
        int weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    static boolean visited[];
    static int column;
    static int branch , R;
    static List<Node>[] listNode;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");

        int N = Integer.parseInt(tk.nextToken());
        R = Integer.parseInt(tk.nextToken());

        column = 0;
        branch = 0;
        visited = new boolean[N + 1];
        listNode = new ArrayList[N + 1];

        for (int i = 0; i < listNode.length; i++) {
            listNode[i] = new ArrayList<Node>();
        }

        for (int i = 0; i < N - 1; i++) {
            tk = new StringTokenizer(in.readLine(), " ");
            int a = Integer.parseInt(tk.nextToken());
            int b = Integer.parseInt(tk.nextToken());
            int d = Integer.parseInt(tk.nextToken());
            listNode[a].add(new Node(b, d));
            listNode[b].add(new Node(a, d));
        }

        visited[R] = true;
        dfs(false, R, 0);
        System.out.println(column + " " + branch);
    }

    private static void dfs(boolean check, int idx, int cnt) {
        if (!check && listNode[idx].size() > 2 || (idx == R && listNode[idx].size() >= 2)) { // 기가노드 처음 발견
            check = true;
            for (int i = 0; i < listNode[idx].size(); i++) {
                if (!visited[listNode[idx].get(i).node]) {
                    visited[listNode[idx].get(i).node] = true;
                    cnt = listNode[idx].get(i).weight; // 초기화 되서 들어가야함
                    branch = Math.max(branch, cnt);
                    dfs(check, listNode[idx].get(i).node, cnt);
                    cnt -= listNode[idx].get(i).weight;
                }
            }
        } else if (!check) {
            for (int i = 0; i < listNode[idx].size(); i++) {
                if (!visited[listNode[idx].get(i).node]) {
                    visited[listNode[idx].get(i).node] = true;
                    cnt += listNode[idx].get(i).weight;
                    column = Math.max(column, cnt);
                    dfs(check, listNode[idx].get(i).node, cnt);
                    cnt -= listNode[idx].get(i).weight;
                }
            }
        } else {
            for (int i = 0; i < listNode[idx].size(); i++) {
                if (!visited[listNode[idx].get(i).node]) {
                    visited[listNode[idx].get(i).node] = true;
                    cnt += listNode[idx].get(i).weight;
                    branch = Math.max(branch, cnt);
                    dfs(check, listNode[idx].get(i).node, cnt);
                    cnt -= listNode[idx].get(i).weight;
                }
            }
        }
    }
}

20924번: 트리의 기둥과 가지