백준 1167번 - 트리의 지름

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

문제

DFS

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

접근법

백준-1967번-트리의-지름 문제와 접근법이 같다.
다만 이 문제의 경우 루트 노드를 주지 않았지만, 임의의 노드를 아무거나 찍고 그 노드에서 가장 멀리 떨어진 노드를 구하고, 구한 노드에서 또다시 멀리 떨어진 노드를 구하는 방식으로 접근하였다.

코드 - JAVA

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


class Main {
    static int N = 0;
    static ArrayList<Pair<Integer,Integer>>[] graph;
    static boolean visit[];
    static int max;
    static int maxIndex;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N+1];
        for(int i=1; i<=N; i++){
            graph[i] = new ArrayList<>();
        }
        visit = new boolean[N+1];
        StringTokenizer str;
        for(int i=0; i<N; i++) {
            str = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(str.nextToken());
            while (str.hasMoreTokens()) {
                int input = Integer.parseInt(str.nextToken());
                if (input == -1)
                    break;
                int value = Integer.parseInt(str.nextToken());
                graph[parent].add(new Pair<>(input,value));
                //주어진 입력이 양방향이라서 한번만 입력함
            }
        }
        dfs(1,0);
        int idx = maxIndex;
        max = 0;
        maxIndex = 0;
        visit = new boolean[N+1];
        dfs(idx,0);
        System.out.print(max);
    }

    public static void dfs(int idx, int sum){
        visit[idx] = true;
        boolean flag = false;
        for(Pair i:graph[idx]){
            if(!visit[(int)i.getKey()]&&(int)i.getKey()!=0){
                flag = true;
                dfs((int)i.getKey(),sum+(int)i.getValue());
            }
        }
        if(!flag&&max<sum){
            max = sum;
            maxIndex = idx;
        }
    }
}

Pair

이전 문제에서도 그렇듯이 계속해서 JavaFX의 Pair를 사용하고 있다.
다른 언어에서 지원하는 Pair와 유사하고, 특별히 메모리를 사용하지 않아 자주 사용하고 있다.
사용법은 다음과 같다.

List<Pair<Integer, Integer>> pairs = new ArrayList<>();

pairs.add(new Pair<>(1,2));

pairs.get(0).getKey();
pairs.get(0).getValue();

사실 Pair는 이름이 직관적이라 자주 사용하긴 했지만, 이는 JavaFx가 포함된 8에서나 사용할만하다.
AbstractMap의 SimpleEntry가 타 언어의 Pair와 거의 같다고 보인다.

• equals(Object o)
• getKey()
• getValue()
• hashCode()
• setValue(V value)
• toString()

위와 같은 함수들을 지원한다.
SimpleEntry 또한 Pair와 같은 형식으로 사용하면 된다.