[백준]20924: 트리의 기둥과 가지 - JAVA

[백준]20924: 트리의 기둥과 가지

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

20924번: 트리의 기둥과 가지

풀이

처음에는 나무 그림이 있길래 직접 트리를 구현하는 문제인가? 싶었는데 읽어보니 그냥 탐색 문제였다. 모든 노드를 탐색하며 조건에 맞는 노드를 찾아주어야 하므로 DFS탐색을 활용하여 문제를 풀었다.

 

DFS알고리즘은 크게 두 함수를 사용하였다. 코드 내용이 매우 유사하여 합치려면 합칠수는 있어보이지만 가독성을 위해 분리하여 구현해 주었다. 하나는 트리의 기둥을 구하는 DFS, 하나는 가장 긴 가지의 길이를 찾는DFS로 구현하였다. 하나씩 살펴보쟝.

 

❌ 노드와 간선의 관계는 방향성이 없다는 것을 유의하자. 나도 이 부분을 신경 써 주지 못해 코드를 다시 수정했다.

 

findPillarDFS(int n, int total) - 트리의 기둥을 구한다.

종료 조건은 기가노드를 만났을때로 설정해 주었다. 

 

기가 노드를 만났을 경우는 다음과 같은 세 가지 경우이다.

1. 자식 노드가 2개 이상일때 (부모 한개, 자식 두개 이상인 경우이므로 연결 노드의 개수는 3개 이상이 된다.)
2. 리프 노드가 동시에 기가 노드일때 (연결 노드의 개수가 부모 하나밖에 없으며 루트가 아니다.)
3. 루트 노드가 동시에 기가 노드일때 (루트 이면서 연결 노드의 개수가 3개 이상이다.)

위 경우를 만났다면, 현재까지 탐색하며 얻은 cost의 합을 트리의 기둥 값으로 지정해 주고 기가 노드를 현재 노드로 설정한 다음 return한다.

 

위의 경우가 아니라면 연결된 노드로 탐색을 계속 진행하되, 부모를 다시 방문하지 않기 위해 visited값을 확인하며 방문한다.

 

findMaxDFS(int n, in total) - 가장 긴 가지의 길이를 구한다.

종료 조건은 리프노드를 만났을 때이다. 리프 노드를 만나면 max값과 현재까지 구한 가지의 최대 길이 값 중 더 큰값을 max값으로 설정해 준다.

 

리프노드일 때는 다음과 같은 한 가지 경우밖에 존재하지 않는다.

1. 연결 노드가 1개일때 (부모와 연결된 간선밖에 존재하지 않는다.)

위의 경우가 아니라면 연결된 노드로 탐색을 진행한다. 이때 방문하지 않았던 노드들을 방문하되, total값을 계산할 때 방문 후 다시 다른 경로로 방문될 수 있기 때문에 visited 와 total값을 다시 설정해 주도록 한다.

 

😜 트리의 기둥을 구한 후 가장 긴 가지의 길이를 구할 때 visited 함수를 다시 초기화 하지 않아도 된다. 가장 긴 가지의 길이를 구할 때는 기가 노드부터 시작하여 다시 부모로 올라가는 경우는 어짜피 답이 되지 않으므로 트리의 기둥을 구하면서 방문한 노드들의 방문 여부는 초기화 해 주지 않아도 된다.  

 

코드

import java.util.*;
 
public class Main {
 
    static int n, r; 
    static int pillar, max, gigaNode;
    static boolean[] visited;
    static ArrayList<Node>[] nodeList;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        r = scan.nextInt();
 
        nodeList = new ArrayList[n + 1];
        for(int i = 1; i < n + 1; i++) {
            nodeList[i] = new ArrayList<>();
        }
 
        for(int i = 0; i < n - 1; i++) {
            int n1 = scan.nextInt();
            int n2 = scan.nextInt();
            int cost = scan.nextInt();
            nodeList[n1].add(new Node(n2, cost));
            nodeList[n2].add(new Node(n1, cost));
        }
 
        pillar = 0;
        max = 0;
        if(n != 1) {
            visited = new boolean[n + 1];
            findPillarDFS(r, 0); 
            findMaxDFS(gigaNode, 0);
        }
 
        System.out.println(pillar + " " + max);
    }
 
    public static void findPillarDFS(int n, int total) {
        if (nodeList[n].size() > 2 || (nodeList[n].size() == 1 && n != r) || (nodeList[n].size() == 2 && n == r)) {
            pillar = total;
            gigaNode = n;
            return;
        }
 
        for (int i = 0; i < nodeList[n].size(); i++) {
            Node next = nodeList[n].get(i);
            if (!visited[next.num]) {
                visited[next.num] = true;
                findPillarDFS(next.num, total + next.cost);
            }
        }
    }
 
    public static void findMaxDFS(int n, int total) {
        if (nodeList[n].size() == 1) { // 리프 노드라면
            max = Math.max(max, total);
            return;
        }
 
        for (int i = 0; i < nodeList[n].size(); i++) {
            Node next = nodeList[n].get(i);
            if (!visited[next.num]) {
                visited[n] = true;
                total += next.cost;
                findMaxDFS(next.num, total);
                total -= next.cost;
                visited[n] = false;
            }
        }
    }
 
    public static class Node {
        int num;
        int cost;
 
        public Node(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }
}