[백준] no1967: 트리의 지름

문제

* 트리의 지름 = 두 노드 사이의 거리가 가장 긴 경로를 구하는 것
* 즉, Node A -> Node B 의 이동에 따른 비용이 다 다르므로,
* 모든 노드를 대상으로, 둘 사이가 이동이 가능할 때, 최대 비용 경로를 구하는 것

문제 링크 : https://www.acmicpc.net/problem/1967

---

원리

1. BFS + PriorityQueue + Integer[][] 사용

2. DFS + ArrayList<Node>형 배열 사용

 

* 주의할 점 : 문제의 조건에서 최대 노드의 개수가 10000이므로, 10000 x 10000을 감당할 수 있어야함. 즉, 비용을 저장하고 탐색하기위해 일반적인 이중 배열을 사용하면 메모리 초과 발생

---

풀이방법

BFS + PriorityQueue 방식

1. 각 출발지점과 목표지점을 순차적으로 지정해 BFS 탐색한다.

2. 이때, 탐색에 사용하는 대기열은 비용의 합이 큰 순으로 정렬되게끔 하고,

    방문한 적이 있거나(visited[현재지점][다음지점]이 true), 경로가 없는 경우(map[현재지점][다음지정]이 null)는

    탐색하지 않는다.

 

3. 따라서, 목표지점에 가장 먼저 도달한 합산은 곧 최대 합산이 된다.

 

DFS + ArrayList<Node>형 배열 방식

원리는 위와 유사함.

단, 특정 출발지점에 대해서 도달 가능한 말단까지 이동하는 경우마다 Max값을 갱신하며,

자료구조를 사용해 메모리 제한이 완화됨.

또한, 위의 단순 배열 탐색 방식에서 Null 여부 판단한것과 달리, Node객체가 있는지 없는지 판별할 필요가 없음.

따라서 메모리를 줄일 수 있음.

 

 

---

나의 코드

시도1. [로컬 성공 / 백준 실패] BFS + PriorityQueue

문제 :모든 경우에 대해서 객체를 만들어가며 탐색하므로, 메모리가 상당히 소모된다. (최대 10000 x 10000의 노드 탐색)

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, max; // 노드의 개수
    private static Integer[][] map; // Null 인경우를 경로가 없는 것으로 처리하기 위함
    private static boolean[][] visited;

    
    public static void main (String[] args) throws IOException {
         N = Integer.parseInt(br.readLine());
         map = new Integer[N+1][N+1];
         max = Integer.MIN_VALUE;

         for(int i=1 ; i<N; i++) {  // 조건이 N-1만큼의 간선(Edge)가 주어짐
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            map[A][B] = map[B][A] = Integer.parseInt(st.nextToken()); // 트리의 경우 방향이 없으므로 양방향 모두 같은 비용으로 저장
         }

         for( int departue = 1 ; departue<=N ; departue++ ) {
            for( int arrival = 1 ; arrival<=N ; arrival++ ) {
                visited = new boolean[N+1][N+1];
                BFS(departue, arrival);
            }
         }
         System.out.println(max);
    }

    private static void BFS(int start, int goal) {
        int result = Integer.MIN_VALUE;
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> b.Sum - a.Sum); // 최대 합계를 구해야 하므로, 내림차순 정렬
        pq.add(new Node(start, 0));
        visited[start][start] = true;

        while(!pq.isEmpty()) {
            Node now = pq.poll();

            if(now.Now == goal) {
                result = now.Sum;
                break;
            }

            for(int next=1 ; next<=N ; next++) {
                if(!visited[now.Now][next] && map[now.Now][next]!=null) {
                    visited[now.Now][next] = true;
                    pq.add(new Node(next, now.Sum + map[now.Now][next]));
                }
            } 
        }

        if(result>=max) max = result;
    }

    private static class Node {
        private int Now;
        private int Sum;

        public Node (int now, int sum) {
            this.Now = now;
            this.Sum = sum;
        }
    }

 

시도2. [로컬 성공 / 백준 실패] : DFS + 1차원 배열 탐색(1중 반복 + 1중 반복)

: 필자의 경우 2차원 배열을 이용해 풀이했으나, 10000 x 10000이라는 경우에 대해 메모리 초과가 발생하는 것 같다.

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, max; // 노드의 개수
    private static Integer[][] map; // Null 인경우를 경로가 없는 것으로 처리하기 위함
    private static boolean[] visited;

    
    public static void main (String[] args) throws IOException {
         N = Integer.parseInt(br.readLine());
         map = new Integer[N+1][N+1];
         max = Integer.MIN_VALUE;

         for(int i=1 ; i<N; i++) {  // 조건이 N-1만큼의 간선(Edge)가 주어짐
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            map[A][B] = map[B][A] = Integer.parseInt(st.nextToken()); // 트리의 경우 방향이 없으므로 양방향 모두 같은 비용으로 저장
         }

        /**
         * 각 Node를 순차적으로 DFS 탐색
         * DFS에서 모든 경우를 탐색하되, 최대값이 되는 경우를 max에 저장
         */

         for(int start = 1 ; start<=N ; start++) {
            visited = new boolean[N+1];
            visited[start] = true;
            DFS(start, 0);
         }

         System.out.println(max);
    }

    private static void DFS(int departue, int cost) {
        for(int next=1 ; next<N+1 ; next++) {
            if(!visited[next] && map[departue][next]!=null) {
                visited[next] = true;
                DFS(next, cost + map[departue][next]);
            }
        }

        max = (max < cost) ? cost : max;
    }

 

 

시도 3. [성공] : DFS + ArrayList<Node> 배열

: 자료구조의 경우 메모리가 크기가 커서 메모리초과가 발생하지 않았다.

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, max; // 노드의 개수
    private static List<Node> map[];
    private static boolean[] visited;

    
    public static void main (String[] args) throws IOException {
         N = Integer.parseInt(br.readLine());
         max = Integer.MIN_VALUE;

         map = new ArrayList[N+1];
         for(int i = 1 ; i<=N ; i++ ) map[i] = new ArrayList<>(); // 주어지는 A->B 노드 이동당 비용을 저장할 것임

         for(int i=1 ; i<N; i++) {  // 조건이 N-1만큼의 간선(Edge)가 주어짐
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            // 방향이 없는 트리이므로, 양방향 같은 비용으로 저장
            map[A].add(new Node(B, cost));
            map[B].add(new Node(A, cost));
         }

        /**
         * 각 Node를 순차적으로 DFS 탐색
         * DFS에서 모든 경우를 탐색하되, 최대값이 되는 경우를 max에 저장
         */

         for(int start = 1 ; start<=N ; start++) {
            visited = new boolean[N+1];
            visited[start] = true;
            DFS(start, 0);
         }

         System.out.println(max);
    }

    private static void DFS(int departue, int sum) {
        // 더이상 갈 곳이 없을때까지(visited[]내 모든 노드를 방문한 경우) 재귀 진행
        for(Node next : map[departue]) { // 직전에 출발한 곳으로부터 이동할 수 있는 모든 경로를 탐색
            if(!visited[next.Num]) { // 방문한 적이 없는 경우에 한해서 (빙빙 도는거 방지)
                visited[next.Num] = true; // 방문체크 후,
                DFS(next.Num, sum + next.Cost);  // 이동, 직전까지 합산 + 새로운 이동을 위한 비용 추가
            }
        }

        max = (max < sum) ? sum : max; // 마지막으로 저장한 최대값과 현재 합산을 비교해서 더 큰값을 저장
    }

    private static class Node {
        private int Num, Cost;

        public Node(int num, int cost) {
            this.Num = num;
            this.Cost = cost;
        }
    }

---

레퍼런스 코드

참고 링크 : https://ilmiodiario.tistory.com/148