[JAVA] 1167번: 트림의 지름 ( 초급 2-57 ) - fail

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

 

문제 풀이

지름의 문제를 구하는 방법은

1번 노드에서 가장 멀리 떨어진 노드를 구한다.

구한 노드에서 다시 가장 먼 노드까지의 거리가 지름의 거리라고 할 수 있다.

이 문제는 bfs를 두번 이용하면 해결할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon1167_2 {
    private static ArrayList<ArrayList<NodeRelationInfo>> nodeRelationInfos;
    private static boolean[] visit;
    private static int maximumDistance = 0;
    private static int maximumDistanceNode = 0;
    private static int n;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nodeRelationInfos = new ArrayList<>();
        visit = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            nodeRelationInfos.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n; j++) {
                int node2 = Integer.parseInt(st.nextToken());
                if (node2 == -1) {
                    break;
                }
                int distance = Integer.parseInt(st.nextToken());
                nodeRelationInfos.get(node1).add(new NodeRelationInfo(node2, distance));
            }
        }

        visit[1] = true;
        bfs1167_findMaximumDistance(1, 0);

        maximumDistance = 0;
        visit = new boolean[n + 1];
        visit[maximumDistanceNode] = true;
        bfs1167_findMaximumDistance(maximumDistanceNode, 0);
        System.out.println(maximumDistance);
    }

    private static void bfs1167_findMaximumDistance(int currentNode, int distance) {
        Queue<NodeRelationInfo> queue = new LinkedList<>();
        queue.add(new NodeRelationInfo(currentNode, distance));

        while (!queue.isEmpty()) {
            NodeRelationInfo nodeRelationInfo = queue.remove();
            currentNode = nodeRelationInfo.node;
            distance = nodeRelationInfo.distance;

            for (NodeRelationInfo nextNodeRelationInfo : nodeRelationInfos.get(currentNode)) {
                int nextNode = nextNodeRelationInfo.node;
                int nextNodeDistance = nextNodeRelationInfo.distance;

                if (!visit[nextNode]) {
                    visit[nextNode] = true;
                    queue.add(new NodeRelationInfo(nextNode, distance + nextNodeDistance));
                    if (maximumDistance < distance + nextNodeDistance) {
                        maximumDistance = distance + nextNodeDistance;
                        maximumDistanceNode = nextNode;
                    }
                }
            }
        }
    }
}

class NodeRelationInfo {
    int distance;
    int node;

    public NodeRelationInfo(int node, int distance) {
        this.node = node;
        this.distance = distance;
    }

    public void setDistance(int distnace) {
        this.distance += distnace;
    }
}

 

포스트 오더를 이용해서 문제를 해결할 수도 있다.

dfs 방법이라고 할 수 있는데

자식 노드의 결과를 부모 노드에서 확인하여 문제를 해결한다.

자식 노드에서 확인해야 할 결과는 두 가지가 존재한다.

 

자식 노드에서 가장 긴 지름이 존재하는지

자식 노드에서 최장 반지름의 길이

 

두개의 정보를 이용하면 문제를 수월하게 해결할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class baekjoon1167_3 {
    private static ArrayList<ArrayList<CurrentNodeToNextNodeRelationInfo1167_3>> nodeInfo;
    private static boolean[] visit;
    private static int maximumDistance = 0;
    private static int maximumDistanceNode = 0;
    private static int n;
    private static int result = 0;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nodeInfo = new ArrayList<>();
        visit = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            nodeInfo.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());

            for (int j = 0; j < n; j++) {
                int node2 = Integer.parseInt(st.nextToken());
                if (node2 == -1) {
                    break;
                }
                int distance = Integer.parseInt(st.nextToken());
                nodeInfo.get(node1).add(new CurrentNodeToNextNodeRelationInfo1167_3(node2, distance));
            }
        }
        visit[1] = true;
        NodeInfo1167_3 nodeInfo = dfs1167_3(1);
        System.out.println(Math.max(Math.max(nodeInfo.radius, nodeInfo.diaMeter), result));
    }

    private static NodeInfo1167_3 dfs1167_3(int currentNode) {

        // 하위 노드들의 정보를 취합
        ArrayList<Integer> radiuses = new ArrayList<>();
        for (CurrentNodeToNextNodeRelationInfo1167_3 cur2nextInfo : nodeInfo.get(currentNode)) {
            int nextNode = cur2nextInfo.node;
            int distance = cur2nextInfo.distance;

            if (!visit[nextNode]) {
                visit[nextNode] = true;
                NodeInfo1167_3 nextNodeInfo = dfs1167_3(nextNode);
                int radius = nextNodeInfo.radius;
                int diaMeter = nextNodeInfo.diaMeter;
                radiuses.add(radius + distance);

                if (diaMeter > result) {
                    result = diaMeter;
                }
            }
        }

        Collections.sort(radiuses, Collections.reverseOrder());
        int currentNodeMaximumRadius = 0;
        int currentNodeMaximumDiamMeter = 0;

        if (radiuses.size() >= 1) {
            currentNodeMaximumRadius = radiuses.get(0);
        }

        if (radiuses.size() >= 2) {
            currentNodeMaximumDiamMeter = radiuses.get(0) + radiuses.get(1);
        }

        return new NodeInfo1167_3(currentNodeMaximumDiamMeter, currentNodeMaximumRadius);
    }
}

class NodeInfo1167_3 {
    int diaMeter;
    int radius;

    public NodeInfo1167_3(int diaMeter, int radius) {
        this.diaMeter = diaMeter;
        this.radius = radius;
    }
}

class CurrentNodeToNextNodeRelationInfo1167_3 {
    // 현재 노드로 부터 떨어진 targetNode의 정보
    int distance;
    int node;

    public CurrentNodeToNextNodeRelationInfo1167_3(int node, int distance) {
        this.node = node;
        this.distance = distance;
    }

    public void setDistance(int distnace) {
        this.distance += distnace;
    }
}