(백준) 트리의 기둥과 가지 - 20924

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

20924번: 트리의 기둥과 가지

 

🐢풀이

일단 트리 구조임을 알 수 있으므로 인접리스트로 트리 구조를 구현했다. 이후 기둥을 구하는 부분과 기가(G)에서 가지를 구하는 부분으로 나눠서 접근했다.

 

무엇보다 주어지는 간선의 정보가 방향이 아닌 무방향이므로 양방향으로 연결시켜줘야 했고, 따라서 각 노드에 대한 방문 체크를 위해 배열도 선언해주었다. 

 

먼저 루트노드(R)에서 기둥을 탐색하고, 해당 기둥에 대한 탐색이 끝나면 방문 체크는 유지한채 기가노드(G)에서 가장 긴 가지를 찾기위한 탐색을 진행했다. 이때 방문을 하지 않은 가지의 개수를 세서 해당 개수가 0일 경우 leaf노드이므로 해당 부분을 위한 leafCount()함수를 만들어서 확인했다.

 

🐢 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, R, G;
    static long Max;
    static boolean[] visited;
    static ArrayList<Node>[] adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
 
        N = Integer.parseInt(input[0]);
        R = Integer.parseInt(input[1]);
        visited = new boolean[N + 1];
        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }
 
        for (int i = 1; i < N; i++) {
            input = br.readLine().split(" ");
            int from = Integer.parseInt(input[0]);
            int to = Integer.parseInt(input[1]);
            int dist = Integer.parseInt(input[2]);
            adj[from].add(new Node(to, dist)); // 무방향이므로 양방으로 이어준다
            adj[to].add(new Node(from, dist));
        }
 
        long treeH = treeHeigth(R, 0); // 기둥
        long longestL = leafLen(G, 0); // 가장 긴 가지
        System.out.printf("%d %d", treeH, longestL);
    }
 
    private static long leafLen(int root, long len) {
        if (leafCount(root) == 0) return len; // leaf노드 인 경우
 
        for (Node next : adj[root]) { // 가지를 탐색 하면서 가장 긴 길이 갱신
            if (!visited[next.n]) {
                visited[next.n] = true;
                Max = Math.max(Max, leafLen(next.n, next.d + len));
            }
        }
        return Max;
    }
 
    private static long treeHeigth(int root, long len) {
        visited[root] = true;
 
        if (leafCount(root) != 1) { // 가지가 없거나, 기둥이 끝난 경우
            G = root;
            return len;
        } else {
            for (Node next : adj[root]) {
                if (!visited[next.n]) {
                    return treeHeigth(next.n, len + next.d);
                }
            }
        }
        return -1;
    }
 
    private static int leafCount(int node)
    {
        int count = 0;
        for (Node next : adj[node]) {
            if (!visited[next.n]) count++;
        }
        return count;
    }
 
    private static class Node
    {
        int n;
        int d;
 
        public Node(int n, int d) {
            this.n = n;
            this.d = d;
        }
    }
}
 

 

🐢결론

그래프 문제를 풀때는 꼭! 방향의 유무를 확인하고 시작하도록 하자.