[백준/JAVA] 1967번: 트리의 지름

📖 문제

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

 

 

💡  풀이 방식

• DFS (트리)

1. 2차원 인접 리스트 배열을 만들어 정보를 입력받는다. (양방향으로!)
2. 1~N번의 모든 노드에서 DFS를 수행해 거리(가중치들의 합 = 트리의 지름)를 계산한다.

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

 

 

 

[DFS 함수]

현재 정점과 연결된 모든 점을 방문하며 가중치를 더하고, 이를 최댓값과 비교해 정답을 가장 큰 값으로 갱신한다.

private static void dfs(int idx, int sum) {
    answer = Math.max(answer, sum);

    for(Node next : list[idx]) {
        if(!visited[next.idx]) {
            visited[next.idx] = true;
            dfs(next.idx, sum + next.v);    // 지름 값 갱신
            visited[next.idx] = false;       
        }
    }
}

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static List<Node>[] list;
    static boolean[] visited;
    static int answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        list = new ArrayList[N+1];
        for(int i = 0 ; i <= N ; i++)
            list[i] = new ArrayList<>();
        
        for(int i = 0 ; i < N-1 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            // 양방향
            list[from].add(new Node(to, v));
            list[to].add(new Node(from, v));
        }
        
        // 모든 노드에서 DFS 수행해 거리 계산
        for(int i = 1 ; i <= N ; i++) {
            visited = new boolean[N+1];
            visited[i] = true;
            dfs(i, 0);
        }
        
        System.out.println(answer);
    }
    
    private static void dfs(int idx, int sum) {
        answer = Math.max(answer, sum);
        
        for(Node next : list[idx]) {
            if(!visited[next.idx]) {
                visited[next.idx] = true;
                dfs(next.idx, sum + next.v);    // 지름 값 갱신
                visited[next.idx] = false;       
            }
        }
    }
}
 
class Node {
    int idx, v;
    
    public Node(int idx, int v) {
        this.idx = idx;
        this.v = v;
    }
}
 

 

 

---

💦 어려웠던 점

- 모든 점에서 DFS 수행할 생각을 하지 못 했다ㅎ (트리 문제 넘 오랜만이라ㅠ)

- dfs 함수 첫번쨰 파라미터에 idx + 1를 넣었다. 근데 그게 아니고 next.idx를 넣어야 한다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 1967. 트리의 지름 (자바 JAVA)

 

[백준 1967] 트리의 지름- JAVA