1. 문제 설명

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

2. 접근 방식

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

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

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

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