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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1167번: 트리의 지름

---

2. 내가 푼 방법

임의의 노드(A)에서 가장 먼 노드(B)를 찾는다. 그 후, 해당 노드(B)에서 다시 가장 먼 노드(C)를 찾을 경우에 두 번의 그래프 탐색으로 트리의 지름을 찾을 수 있다.

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1167.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static List<Tuple>[] list;
    static int farV;
    static int result;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        result = Math.max(result, bfs(1));
        result = Math.max(result, bfs(farV));
    }

    public static int bfs(int s) {
        int max = 0;

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(s, 0));

        boolean[] visit = new boolean[N+1];

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int v = t.v;
            int w = t.w;

            if (visit[v]) continue;
            else visit[v] = true;
            
            if (max < w) {
                max = w;
                farV = v;
            }

            for (Tuple tuple : list[v]) {
                queue.add(new Tuple(tuple.v, w + tuple.w));
            }
        }

        return max;
    }

    public static class Tuple {
        int v;
        int w;

        public Tuple(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N+1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());

            while (true) {
                int v2 = Integer.parseInt(st.nextToken());

                if (v2 == -1) break;
                else {
                    int w = Integer.parseInt(st.nextToken());
                    list[v1].add(new Tuple(v2, w));
                    list[v2].add(new Tuple(v1, w));
                }
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

메모리 초과와 시간 초과에 유의해서 풀어야 했던 문제이다. 처음에는 갔던 경로를 다시 가면 안된다는 생각에 사로잡혀 삽질을 했는데,, 그냥 탐색 자체를 두 번으로 줄임으로써 해결할 수 있었다.