백준 1967번 - 트리의 지름

solved.ac 백준 골드문제 포스팅

문제

DFS

깊이 우선 탐색, 그래프의 자식을 우선으로 탐색한다.
추후 다른 포스팅에서 BFS와 함께 정리 예정

접근법

지름을 구할 때 가장 서로 멀리 떨어져 있는 두 노드를 구해야 한다.
-> 처음으로는 루트 노드에서 가장 멀리 떨어진 노드를 구한다. (이 때 DFS 또는 BFS를 통한 탐색 수행)
-> 다음으로는 구한 노드에서 가장 멀리 떨어진 노드를 구한다. (탐색 수행)
이렇게 두 번의 DFS로 문제를 해결할 수 있다.

주의

문제에서 보다시피 최대 노드 개수가 만개이다. 메모리를 조금이나마 비효율적으로 사용하게 되면 바로 메모리 제한에 걸리게 된다.
-> 그래프를 행렬로 표현하기보다는 인접 리스트 형태로 표현하는게 옳다.
(그래프를 HashMap으로 구현하여도 메모리 제한을 초과한다.)

코드 - JAVA

import javafx.util.Pair;
import java.io.*;
import java.util.*;


class Main {
    static ArrayList<Pair<Integer,Integer>> edges[];
    static boolean visit[];
    static int max = 0;
    static int maxIndex = 0;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        edges = new ArrayList[N+1];
        for(int i=0; i<edges.length; i++){
            edges[i] = new ArrayList<>();
        }
        for(int i = 0 ; i < N-1 ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            edges[parent].add(new Pair<>(child,dist));
            edges[child].add(new Pair<>(parent,dist));
            //그래프를 양방향 그래프로, 리스트의 형태로 담음
        }
        visit = new boolean[N+1];
        dfs(1,0);
        //Root 노드에서 제일 멀리 떨어진 노드 찾기
        int start = maxIndex;
        maxIndex = 0;
        max = 0;
        visit = new boolean[N+1];
        dfs(start,0);
        //지름을 구하기 위한 노드를 찾기
        System.out.print(max);
    }

    public static void dfs(int start, int weight){
        visit[start] = true;
        if(!edges[start].isEmpty()){
            for(Pair child : edges[start]){
                if(!visit[(int) child.getKey()]){
                    if(max<weight+(int)child.getValue()){
                        max = weight+(int)child.getValue();
                        maxIndex = (int)child.getKey();
                    }
                    dfs((int)child.getKey(), weight+(int)child.getValue());
                }
            }
        }
    }
}