[JAVA] 백준 1167 - 트리의 지름

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

1967번 트리의 지름 문제랑 동일한 개념을 다루는 문제로, 다익스트라 및 DFS를 이용해 푸는 문제이다.

정점의 개수가 10배인 것만 제외하면 세부사항도 같다.

먼저 첫번째 다익스트라로 임의의 정점에서 가장 먼 정점을 찾고, 가장 먼 정점을 기준으로 다익스트라를 돌려 나온 가장 먼 정점과의 거리를 구하면 되는 문제이다.

일반적으로 Node 클래스 내에 ArrayList로 간선을 저장하는 걸 선호해왔는데, 이번엔 int 2차원 배열로 해보자~ 했다가 메모리초과가 나서 계산해보니 10만*10만칸의 int는 약 40GB를 차지한다. 쓰던 방식을 계속 써야겠다.

1967번과 똑같이 골드 4문제 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = par(br.readLine());
        List<TreePos> nodeList = new ArrayList<>();
        for (int i = 0; i <= size; i++) {
            nodeList.add(new TreePos(i));
        }
        nodeList.get(1).weight = 0;
        for (int i = 0; i < size; i++) {
            int[] temp = getArray(br.readLine());
            int targetNode = temp[0];
            TreePos target = nodeList.get(targetNode);
            for (int j = 1; j < temp.length-1; j += 2) {
                target.add(new int[]{temp[j], temp[j + 1]});
            }
        }
        PriorityQueue<TreePos> pq = new PriorityQueue<>();

        boolean[] visited = new boolean[size + 1];
        pq.offer(nodeList.get(1));
        while (!pq.isEmpty()) {
            TreePos pos = pq.poll();
            int value = pos.value;
            int weight = pos.weight;
            if (visited[value]) continue;
            visited[value] = true;
            for (int i = 0; i < pos.map.size(); i++) {
                int targetNode = pos.map.get(i)[0];
                if (pos.map.get(i)[1] == 0 || visited[targetNode]) continue;
                TreePos target = nodeList.get(targetNode);
                if (pos.map.get(i)[1] + weight < target.weight) {
                    target.weight = pos.map.get(i)[1] + weight;
                    pq.offer(target);
                }
            }
        }
        int max = -1;
        int midx = -1;
        for (int i = 1; i <= size; i++) {
            if (nodeList.get(i).weight > max) {
                max = nodeList.get(i).weight;
                midx = i;
            }
            nodeList.get(i).weight = Integer.MAX_VALUE;
        }
        Arrays.fill(visited, false);
        TreePos st = nodeList.get(midx);
        st.weight = 0;
        pq.offer(st);
        while (!pq.isEmpty()) {
            TreePos pos = pq.poll();
            int value = pos.value;
            int weight = pos.weight;
            if (visited[value]) continue;
            visited[value] = true;
            for (int i = 0; i < pos.map.size(); i++) {
                int targetNode = pos.map.get(i)[0];
                if (pos.map.get(i)[1] == 0 || visited[targetNode]) continue;
                TreePos target = nodeList.get(targetNode);
                if (pos.map.get(i)[1] + weight < target.weight) {
                    target.weight = pos.map.get(i)[1] + weight;
                    pq.offer(target);
                }
            }
        }
        max = -1;
        for (int i = 1; i <= size; i++) {
            if (nodeList.get(i).weight > max) {
                max = nodeList.get(i).weight;
            }
        }
        System.out.println(max);
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class TreePos implements Comparable<TreePos> {
    int value;
    int weight = Integer.MAX_VALUE;
    ArrayList<int[]> map = new ArrayList<>();
    TreePos(int value) {
        this.value = value;
    }
    void add(int[] vertex){
        this.map.add(vertex);
    }
    @Override
    public int compareTo(TreePos other) {
        return this.weight - other.weight;
    }
}