[백준] 1167 트리의 지름 java

1. 문제 설명

[문제 링크](https://www.acmicpc.net/problem/1167)

2. 접근 방식

임의의 정점에서 제일 먼 정점은 트리의 지름이 되는 두 개의 점 중 하나이다.

라는 아이디어를 기반으로 문제를 푼다. (위의 Idea가 이해가 안된다면, 한번 예시를 가지고 해보면 된다. 어느 정점에서 출발하든, 그 정점의 제일 먼 정점은 트리의 한 축이다.)

1. 시작 정점을 입력하면, 제일 먼 정점과 그까지 갈 때의 거리를 반환하는 bfs 함수를 만든다.
2. 해당 함수에 임의의 정점 (제 풀이에선 1)을 넣고, 트리의 지름이 되는 정점을 구한다.
3. 반환 받은 정점을 다시 bfs 함수에 입력해서, 입력 정점에서 제일 먼 정점과 그까지 갈 때의 거리를 반환 받는다.
4. 해당 거리를 출력한다.

3. 코드 분석

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

public class Main {
    static int V;
    static ArrayList<Node> [] list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(br.readLine());

        list = new ArrayList[V+1];

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

        for (int i = 0; i < V; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            while (st.hasMoreTokens()){
                int end = Integer.parseInt(st.nextToken());
                if(end == -1) break;
                int weight = Integer.parseInt(st.nextToken());
                list[start].add(new Node(end, weight));
            }
        }
        Node far_node  = bfs(1);
        Node ans_node = bfs(far_node.v);
        System.out.println(ans_node.w);
    }
    // 현 노드에서 제일 먼 Node 출력
    public static Node bfs (int start) {
        int max_vertex = 0;
        int max_weight = 0;
        boolean [] isVisited = new boolean[V+1];
        ArrayDeque<Node> aq1 = new ArrayDeque<>();

        aq1.add(new Node(start, 0));
        isVisited[start] = true;

        while (!aq1.isEmpty()){
            Node now = aq1.poll();
            if(now.w > max_weight){
                max_vertex = now.v;
                max_weight = now.w;
            }
            for (int i = 0; i < list[now.v].size(); i++) {
                Node next = list[now.v].get(i);
                if(!isVisited[next.v]){
                    isVisited[next.v] = true;
                    aq1.add(new Node(next.v, now.w + next.w));
                }
            }

        }

        return  new Node(max_vertex, max_weight);
    }
}

class Node {
    int v;
    int w;

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

4. 성장 하기

나는 미방문 정점의 Node 클래스를 새로 만들어서, 해당 Node 객체의 w(가중치)에 지금까지 들었던 비용을 누적시켜서 계산했다. 이런 식으로 매번 새로 메모리 할당을 하다보니, 전체 메모리 사용이 많았다. Do it 알고리즘 풀이에서는 BFS 함수에는 정점의 index만 넣고, distance 배열이라는 누적 가중치 배열을 만들어서 계산했다.

distance 배열

123456

0

0

0

0

0

0

시작 정점의 번호를 `2`라 하자. 2에서 만약 정점 4로 갔을 때 가중치가 3이 들었다면 이를 distance 배열에 누적한다. distance[4]는 시작 정점에서 정점 번호 4까지 오는 최단 경로의 누적 가중치 값이다.

123456

0

0

0

4

0

0

이제 4번에서는 6번으로만 갈 수 있는데, 이때 드는 가중치가 7이라면 정점`6`은 시작 정점`2`에서 최단 경로로 간다면 총 11이라는 가중치가 드는 것이다. distance[6] = distance[4] + w (4 -> 6으로 갈 때 드는 비용) = 11

123456

0

0

0

4

0

11

이런 식으로 가중치에 대한 배열을 만들어 가중치 따로, BFS를 통한 정점 탐색을 따로 해서 메모리 사용량을 줄였다. 참고하기 좋은 것 같다.