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

문제

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

20924번: 트리의 기둥과 가지

N개의 노드와 N-1개의 간선으로 이루어진 트리가 있다.

이 트리의 루트를 타고 이동하다가, 처음으로 2개 이상의 노드가 연결된 노드가 발견될 경우, 이를 기가 노드라고 하며, 이전 경로를 기둥경로 라고 한다.

기가 노드에서시작해서 기둥 경로를 제외하고, 리프노드까지의 경로를 가지경로라고한다.

 

기둥경로의 길이와 가장 긴 가지경로를 출력하는 문제다.

---

풀이

기본적인 트리문제탐색 문제였다.

로직

트리를 두번 탐색해주는 방식으로 풀었다.

1. 첫번째 탐색에서는 기둥경로의 길이를 구하기위해 루트노드부터 기가노드까지 탐색한다.

소스코드

    private int getPillar(int idx){
        check[idx] = true;
        gigaNode = idx;
        if((idx == R && edges.get(idx).size() > 1) || (idx != R && edges.get(idx).size() != 2) || N == 1) 
            return 0;
        Node nextNode = edges.get(idx).get(0);
        nextNode = (check[nextNode.node] == true) ? edges.get(idx).get(1) : nextNode;
        return getPillar(nextNode.node) + nextNode.weight;
    }

2. 두번째 탐색에서는 가지경로의 길이를 구하기위해, 기가노드부터 모든 리프노드를 한번씩 탐색한다. 이때, 최댓값을 찾야하므로, max값을 리턴받아야함에 주의하자.

    private int getBranch(int idx){
        check[idx] = true;
        int ret = 0;
        for(int i = 0; i < edges.get(idx).size(); i++){
            Node nextNode = edges.get(idx).get(i);
            if(check[nextNode.node]) continue;
            ret = Math.max(ret, getBranch(nextNode.node) + nextNode.weight);
        }
        return ret;
    }

 

양방향 간선으로 구현하지않으면 틀리니 주의하도록하자.

 

반례

7 1
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1

 

답 : 0 2

 

4 1

2 1 100

3 2 10

4 3 1

 

답 : 111 0

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/20924%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EA%B8%B0%EB%91%A5%EA%B3%BC%20%EA%B0%80%EC%A7%80/Main.java

devxb/JJUNalgo