[Java] 백준 1967번 트리의 지름

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

1967번: 트리의 지름

 

참고한 문제풀이 블로그   https://ilmiodiario.tistory.com/148

 

핵심

1 ~ N까지 노드와 연결된 간선정보를 양방향 인접리스트로 표현
→ List<Node> list[]

간선에 가중치가 있어 Node 클래스를 만들어 입력 받음
모든 노드에 대해 각 노드마다 DFS 를 통해 연결된 노드 끝까지 가보며 가중치를 더한다.
그리고 더한 가중치값 중 가장 큰 값이 결과값이 된다.

 

 

키워드

1️⃣  List<Node> list[]
2️⃣  무방향그래프 == 양방향 추가 (부모 ↔️ 자식)
3️⃣  DFS를 통해 탐색하며 가중치 더하기 (1 ~ N 번 노드까지)

 

포인트

// 부모노드, 자식노드, 간선가중치는 List<Node>[] 에 저장한다.
// (List<Node>타입의 원소를 가지는 배열에 저장)
// 무방향 그래프이므로 (부모 - 자식) 양방향으로 저장한다.
// 트리의 지름은 dfs를 이용해 루트노드부터 시작해서 모든노드에서 가장 먼노드까지의 가중치를 계산한다.
// 가중치 중 가장 큰 값을 결과값 변수에 계속 업데이트 해준 뒤 반환한다.

 

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

public class Main {
    static class Node {
        int data, weight;
        Node(int data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    }
    
    static List<Node> gragh[];
    static boolean visited[];
    static int max = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        gragh = new ArrayList[n + 1]; 
        StringTokenizer st;
        
        //초기화
        for(int i = 0; i <= n; i++)
            gragh[i] = new ArrayList<Node>();
        
        //그래프 연결하기
        for(int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int par = Integer.parseInt(st.nextToken());
            int chi = Integer.parseInt(st.nextToken());
            int wei = Integer.parseInt(st.nextToken());
            
            gragh[par].add(new Node(chi, wei));
            gragh[chi].add(new Node(par, wei));
        }
        
        //dfs로 모든 각각의 노드들에서 가장먼 노드까지의 가중치계산
        for(int i = 1; i <= n; i++) {
            visited = new boolean[n + 1];
            visited[i] = true;
            dfs(i,0);
        }
        System.out.println(max);
    }
    
    static void dfs(int cur, int dis) {
        for(Node node : gragh[cur]) {
            if(!visited[node.data]) {
                visited[node.data] = true;
                dfs(node.data, dis + node.weight);
            }
        }
        max = max < dis ? dis : max;
    }
}

 

 

 

 

기억하자 메소-드

✅  offerFirst(), offerLast() : 큐의 처음, 큐의 마지막에 원소 추가

✅  pollFirst(), pollLast() : 큐의 처음, 큐의 마지막 요소를 제거

 

✅   Map.getOrDefault(Object key, V defaultValue) 

key	찾을 키 값
defaultValue	키가 맵에 없을 경우 반환할 기본값
(예시) map.getOrDefault(c,0) + v	키 c가 맵에 없을경우 값을 0으로 설정하고 그게 아니라면 v를 더함