[BOJ/Java] 1967. 트리의 지름

문제링크:  https://www.acmicpc.net/problem/1967

세줄 요ㅇ...

 

• 가중치가 제일 큰 값을 가진 지름을 찾는 문제

 

문제에서 주어진 조건

• 노드 번호 순서대로 주어짐
• 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호

---

 

접근

• 원은 두 점(말단 노드) 사이 길이이다
• 그 중 제일 긴 노드 두 점을 찾으면 된다

DFS를  사용하면 시작 노드에서부터 가장 큰 말단 노드를 찾을 수 있다. 

현재 어떤 노드가 제일 큰 노드인지 알 수 없으니 최상위 부모 노드에서 시작하여  가장 큰 말단 노드부터 찾는다. 

 

1번. DFS로 말단 노드 한 점을 찾는다.

• 최상단 노드는 제일 사이즈가 큰 말단 노드가 아니다. 
• 따라서, 최상위 노드에서 경로가 가장 긴(지름이 제일 긴) 노드를 찾자.
• 1번 노드는 그저 처음 탐색을 위한 노드라고 만 생각하자.

 

2번.  DFS를 한번 더 사용해서, 이제는 시작점이 주어졌으니, 거꾸로 DFS 탐색을 시작한다.

• 끝점부터 모든 경로를 탐색하면서 제일 긴 값을 기록 갱신한다. 

ㅇ

이렇게 하면 정답을 찾을 수 있다. 

 

 

정답 코드

---

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

class Main {
    
    static List<N>[] nList;
    static boolean[] visited;
    static int max;
    static int maxIdx;
    
    static class N {
        int e;
        int cost;

        N(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
    }   

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        nList = new List[N+1];
        for(int i = 0; i <= N; i++) {
            nList[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) {
            String[] in = br.readLine().split(" ");
            int s = Integer.parseInt(in[0]);
            int e = Integer.parseInt(in[1]);
            int cost = Integer.parseInt(in[2]);
            nList[s].add(new N(e,cost));
            nList[e].add(new N(s,cost));
        }
        
        visited = new boolean[N+1];
        visited[1] = true;
        dfs(1,0);

        visited = new boolean[N+1];
        visited[maxIdx] = true;
        dfs(maxIdx, 0);

        System.out.println(max);
    }


    static void dfs(int idx, int val) {
        if(max < val) {
            max = val;
            maxIdx = idx;
        }

        for(N next : nList[idx]) {
            if(!visited[next.e]) {
                visited[next.e] = true;
                dfs(next.e, val + next.cost);
            }
        }
    }
}

 

ETC.

---

dfs을 사용해야 한다는 것을 알았지만,

최상단 노드가 중점으로 생각해서 최상위 노드에서 가장 긴 노드 2개를 선정해서 풀려고 했을때

visited를 어떻게 관리할 수 있을지 생각 하지 못했습니다. 

결국, 정답을 보고 완전히 내것으로 만들어 기록합니다.

 

 

잘못된 내용이나 피드백 남겨주세요!