[백준 1595] - 북쪽나라의 도로 Java

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

1595번: 북쪽나라의 도로

이 문제는 ‘트리의 지름’ 이라는 문제와 유사한 너무 well-known 풀이가 필요하다.

 

만약 내가 실제 코딩 테스트에서 이런 성질을 정확하게 유도해낼 수 있을까? 라고 생각해서 주변에 알고리즘 잘 하는 형에게 의견을 물어봤는데 사실 이런 건 너무 well known이라 공부하면서 꼭 알아둬야 하는 느낌? 테크닉?이라고 한다.

 

 

한창 몇 년 전 수능 수학 할 때의 로피탈 정리로 날먹하는 거라고 생각하면 되려나?? 그 때 생각해보면 강사가 로피탈 제발 좀 쓰지 말라고 하긴 했지만,, ㅋㅎ

 

 

문제에서 요구하는 것을 정리해보면, 각 도시별로 두 개씩 연결이 돼 있는데

가장 길게 연결되어 있는 도로를 찾으라는 것이다.

 

그리고 이 문제는 

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

1167번: 트리의 지름

 

이 문제랑 완전히 똑같이 증명이 가능한 문제다.

 

 

 

그리고 이 문제에서는 힌트까지 제공한다.

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

1967번: 트리의 지름

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

증명

 

 

 

결국 트리의 지름을 찾으려면

임의의 한 점 A에서 다익스트라 알고리즘을 수행하여

A에서 가장 먼 점 B를 찾으면 B는 항상 위 그림에서 원의 지름 위에 있게 된다.

그리고 B에서 다익스트라 알고리즘을 다시 한 번 수행하면, 지름 위에 있는 점 C가 가장 멀리 있을 것이고, 트리의 지름을 구할 수 있게 된다.

 

결국 다익스트라 두 번으로 문제를 풀 수 있게 된다.

 

풀이

가장 먼저 아무 점을 골라 (코드에서는 1번 도시를 고름) 다익스트라를 수행한다.

PriorityQueue<Node> pq = new PriorityQueue<>();
HashMap<Integer, Integer> visited = new HashMap<>();
visited.put(1, 0);
pq.add(new Node(1, 0));
while (!pq.isEmpty()) {
    final Node now = pq.poll();

    if (!visited.containsKey(now.next)) {
        visited.put(now.next, now.cost);
    }
    else if (visited.get(now.next) < now.cost) {
        continue;
    }

    for (Node node : map.get(now.next)) {
        if (visited.get(now.next) < now.cost + node.cost) {
            pq.add(new Node(node.next, node.cost + now.cost));
        }
    }

}

visited에는 각 도시의 거리가 저장돼있을 것이고, visited를 기록해둔 map에서 최댓값을 가지는 도시를 구해준다.

 

Map.Entry<Integer, Integer> entry = visited.entrySet()
				.stream()
				.max(Map.Entry.comparingByValue())
				.get();

이후 구한 최댓값을 가지는 도시에서 또 다시 다익스트라를 수행한다.

pq = new PriorityQueue<>();
visited = new HashMap<>();
visited.put(entry.getKey(), 0);
pq.add(new Node(entry.getKey(), 0));
while (!pq.isEmpty()) {
    final Node now = pq.poll();

    if (!visited.containsKey(now.next)) {
        visited.put(now.next, now.cost);
    }
    
    else if (visited.get(now.next) < now.cost) {
        continue;
    }

    for (Node node : map.get(now.next)) {
        if (visited.get(now.next) < now.cost + node.cost) {
            pq.add(new Node(node.next, node.cost + now.cost));
        }
    }

}

이제 다시 visited에서 최댓값을 찾아서 길이를 출력해주면 된다

entry = visited.entrySet()
        .stream()
        .max(Map.Entry.comparingByValue())
        .get();

System.out.println(entry.getValue());

전체 코드

package 백준_2024년.스터디_5wnck;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class problem5 {
    static class Node implements Comparable<Node> {
        int next, cost;

        public Node(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }
    static HashMap<Integer, ArrayList<Node>> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str;

        boolean flag = false;
        try {
            while ((str = (br.readLine())) != null) {

                st = new StringTokenizer(str);
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                if (!map.containsKey(a)) {
                    map.put(a, new ArrayList<>());
                }
                if (!map.containsKey(b)) {
                    map.put(b, new ArrayList<>());
                }

                map.get(a).add(new Node(b, cost));
                map.get(b).add(new Node(a, cost));
                flag = true;

            }
        }
        catch(Exception e) {

        }
        if(!flag) {
            System.out.println(0);
            return ;
        }
        else {
            PriorityQueue<Node> pq = new PriorityQueue<>();
            HashMap<Integer, Integer> visited = new HashMap<>();
            visited.put(1, 0);
            pq.add(new Node(1, 0));
            while (!pq.isEmpty()) {
                final Node now = pq.poll();

                if (!visited.containsKey(now.next)) {
                    visited.put(now.next, now.cost);
                }

                else if (visited.get(now.next) < now.cost) {
                    continue;
                }

                for (Node node : map.get(now.next)) {
                    if (visited.get(now.next) < now.cost + node.cost) {
                        pq.add(new Node(node.next, node.cost + now.cost));
                    }
                }

            }

            Map.Entry<Integer, Integer> entry = visited.entrySet().stream().max(Map.Entry.comparingByValue()).get();

            pq = new PriorityQueue<>();
            visited = new HashMap<>();
            visited.put(entry.getKey(), 0);
            pq.add(new Node(entry.getKey(), 0));
            while (!pq.isEmpty()) {
                final Node now = pq.poll();

                if (!visited.containsKey(now.next)) {
                    visited.put(now.next, now.cost);
                }

                else if (visited.get(now.next) < now.cost) {
                    continue;
                }

                for (Node node : map.get(now.next)) {
                    if (visited.get(now.next) < now.cost + node.cost) {
                        pq.add(new Node(node.next, node.cost + now.cost));
                    }
                }

            }
            entry = visited.entrySet().stream().max(Map.Entry.comparingByValue()).get();

            System.out.println(entry.getValue());

        }
    }
}