백준 1967번 : 트리의 지름 java

이 문제는 dfs를 이용하여 노드들을 이동할 때 이동한 가중치의 합이 가장 크게 되는 경로의 가중치의 합을 출력하는
문제입니다.

위의 그림과 같이 트리가 있을 때 빨간 선으로 되어 있는 간선들의 가중치의 합이 가장 크므로 이러한 경로를 구하는
알고리즘입니다.

저는 이 문제를 해결하기 위해서 각 경로에서 dfs를 하여 가중치의 합이 가장 클 때를 찾았습니다.

코드를 보면서 추가로 설명드리도록 하겠습니다.

---

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

public class Main {
    static List<Node>[] map;
    static boolean[] visited;
    static int max = Integer.MIN_VALUE;
    static int n;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        map = new List[n+1];

        for(int i = 1; i<=n; i++)
            map[i] = new ArrayList<>();

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

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            map[start].add(new Node(end, val));
            map[end].add(new Node(start, val));
        }

        dfs();

        System.out.println(max);
    }

    static void dfs(){
        for(int i = 1; i<=n; i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(i, 0);
                visited[i] = false;
            }
        }
    }

    static void dfs(int ex, int sum){
        for(int i = 0; i<map[ex].size(); i++){
            Node next = map[ex].get(i);
            int nextGo = next.go;
            int val = next.val;

            if(!visited[nextGo]){
                visited[nextGo] = true;
                dfs(nextGo, sum + val);
                visited[nextGo] = false;
            }
        }

        max = Math.max(max, sum);
    }
}

class Node{
    int go, val;

    Node(int go, int val){
        this.go = go;
        this.val = val;
    }
}

이 문제를 풀 때 ArrayList를 사용한 이유는 메모리가 부족하기 때문입니다.

아래의 링크에 들어가면 이와 유사한 문제가 있어 이에 대한 설명이 되어 있습니다.

백준 1753번 : 최단경로 java

이것을 제외하면 단순한 dfs를 이용하는 문제입니다.