문제번호	제목	난이도
1967번	트리의 지름	골드 4

1967번 트리의 지름

해결코드

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

class Node{
    int point;
    int weight;

    public Node(int point, int weight) {
        this.point = point;
        this.weight = weight;
    }
}

public class Main {

    static boolean[] visited;
    static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        List<Node>[] list = new ArrayList[n+1];
        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }


        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list[first].add(new Node(second, weight));
            list[second].add(new Node(first, weight));
        }
        for (int i = 1; i < n + 1; i++) {
            visited = new boolean[n+1];
            visited[i] = true;
            backtracking(list, i,0);
        }

        bw.write(max+"");

        br.close();
        bw.close();
    }

    private static void backtracking(List<Node>[] list, int start, int sum) {
        for(Node n : list[start]){
            if(!visited[n.point]){
                visited[n.point] = true;
                backtracking(list, n.point, sum + n.weight);
            }
        }
        max = Math.max(sum, max);
    }

}

고민과 해결의 시간

1. 일단 이름 그대로 트리로 해결하는 문제이고.. 결국 내가 선택하게 될 가장 큰 가중치의 두 노드는 결국 모두 탐색하면서 발견을 해야한다
2. 또한 중복되지 않도록 해야하므로 visted 방문 배열을 활용하는 백트래킹으로 풀도록 접근하였다
3. 현재 트리는 방향이 없는 그래프이다. 따라서 양방향으로 연결한다
4. Node 클래스를 하나 만들었는데, 가리키는 방향과 가중치를 필드로 갖도록 하였다.
5. 이어서 백트래킹으로 진행하는데 조금 까다로워서 순회로 감싸여진 백트래킹으로 구현하였다
6. 각 순회마다 방문 배열을 초기화하고, 첫 시작점만 true로 바꾼 뒤, 백트래킹을 시작한다
7. 각 백 트래킹에서 주어진 리스트 배열 인덱스의 모든 노드를 탐색한다
8. 이때 만약 해당 노드의 point가 방문하지 않았다면 방문으로 바꾸고 백트래킹을 진행한다. 이때 리스트는 그대로, start는 n.point, 그리고 sum은 sum + n.weight로 가중치를 더하는 형태로 진행해준다
9. 노드 탐색이 끝나면 max 변수에 max와 sum중 더 큰 값을 넣어준다
   10 이 과정을 통해 찾은 max를 출력하면 정답이 된다.

문제 링크:

1967-트리의 지름