JAVA 백준 1967 트리의 지름 (트리)

 

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

---

문제

1. 입력으로 자연수 N ( 1 <= N <= 10000 ) 을 입력받음.
2. 둘째 줄부터 N - 1개의 줄에 간선에 대한 정보(부모 노드, 자식 노드, 간선 가중치(1 <= 간선 가중치 <= 100))가 부모 노드 번호가 작은 것부터, 부모 노드 번호가 같으면 자식 노드 번호가 작은 것이 먼저 입력된다.
3. 루트 노드 번호는 항상 1이다.

---

 

풀이 과정

 

1. 트리이기 때문에 dfs와 bfs 중 무엇을 사용할 것인지 정해야 됨. -> 이 문제는 간선의 가중치를 사용하는 문제이고 경로를 이용하는 문제이기 때문에 dfs를 사용해야 된다.

2. 트리는 양방향으로 연결된 리스트이기 때문에 입력된 내용을 배열로 옮길 때 부모 노드에서 자식 노드로 가거나 자식 노드에서 부모 노드로 갈 수 있도록 양쪽 모두에 해당 노드들을 등록해야 된다.

3. dfs 함수를 만들 때 재귀 함수로 만들 것이기 때문에 간선 가중치의 합을 저장하며 비교할 부분이 필요하다.

4. 트리를 배열로 만들 때 연결될 노드의 값과 가중치를 저장해야 되기 때문에 Node 구조체(클래스)를 만들어 사용했다.

 

 

다른 부분은 다 괜찮았는데 제일 어려운 부분은 dfs에서 어떻게 가중치의 합을 저장하여 비교하는 부분이었다.

트리 문제에서 dfs와 bfs를 구분하여 사용하는 것이나 각 함수를 어떻게 조절해야 되는 것인지 판단하는 게 제일 어려운 것 같다.

 

 

dfs 함수에서는 수정을 고려해봐야 될 부분이 좀 있는 것 같다.

1. dfs 함수 진입 후 바로 나오는 노드의 방문 여부를 체크하는 배열을 수정한 뒤에 나오는 부분.

2. 재귀 함수를 호출할 때의 매개변수 부분.

 

이 두 부분을 잘 수정할 수 있다면 아마 트리 문제를 잘 풀 수 있지 않을까 싶다.

 

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static class Node {
        int data;
        int weight;

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

    static boolean[] visited;
    static int max = 0;

    public static void dfs(ArrayList<Node> list[], int s, int sum) {
        visited[s] = true;
        max = Math.max(max, sum);

        ArrayList<Node> temp = list[s];
        for (int i = 0; i < temp.size(); i++) {
            if (!visited[temp.get(i).data]) {
                dfs(list, temp.get(i).data, sum + temp.get(i).weight);
            }
        }
    }

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

        int N = Integer.parseInt(br.readLine());

        visited = new boolean[N + 1];
        ArrayList<Node>[] list = new ArrayList[N + 1];

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

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

            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            list[parent].add(new Node(child, value));
            list[child].add(new Node(parent, value));
        }

        for (int i = 1; i < N + 1; i++) {
            visited = new boolean[N + 1];
            dfs(list, i, 0);
        }

        System.out.println(max);
    }
}