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

 

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

1167번: 트리의 지름

 

핵심

입력값의 첫번째는 정점 번호고,
이어서 연결된 간선의 정보를 의미하는 정수가 2개씩(정점번호, 거리) 주어진다.
→ 한개의 정점번호에 여러개의 간선정보가 주어질 경우에 그래프에 어떤 방식으로 추가할 것인지를 고민했다.

트리의 지름은 트리에서 임의의 두 점 사이의 거리중 가장 긴것을 의미한다
→ dfs로 트리를 탐색하며 간선의 가중치를 더한다.

 

키워드

1️⃣ List<Node> graph[] 배열을 사용해 트리 생성
2️⃣  두번의 DFS (1 ~ 가장 먼 노드 / 가장 먼 노드에서 다시 가장 먼 노드)

 

포인트

// 트리의 지름
1.  1 ~ 가장먼 노드 DFS
2.  가장먼 노드에서 다시 가장먼 노드 DFS

► List<Node> graph[] 로 트리생성
    이때 while 문과 -1을 이용해 graph에 Node 추가하기

►두번의 DFS를 위해 '가장 먼 노드를 저장하는 변수', '최대가중치 저장변수 생성'

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

public class Main{
    static class Node{
        int num, len;
        Node(int num, int len){
            this.num = num;
            this.len = len;
        }
    }
    
    static List<Node> graph[];
    static boolean[] visited;
    static int max = 0;
    static int far = 0;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int v = Integer.parseInt(br.readLine());
        
        graph = new ArrayList[v + 1];
        for (int i = 1; i <= v; i++)
            graph[i] = new ArrayList<Node>();
        
        StringTokenizer st;
        for(int i = 1; i <= v; i++) {
            st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            
            while(true) {
                int num = Integer.parseInt(st.nextToken());
                if(num == -1) break;
                
                int wei = Integer.parseInt(st.nextToken());
                graph[cur].add(new Node(num, wei));
            }
        }
        
        visited = new boolean[v + 1];
        dfs(1, 0);
        max = 0;
    
        visited = new boolean[v + 1];
        dfs(far, 0);
    
        System.out.println(max);
    }

    static void dfs(int node, int dis) {
        visited[node] = true;
        if(dis > max) {
            max = dis;
            far = node;
        }
        for(Node info : graph[node]){
            if(!visited[info.num]) dfs(info.num, dis + info.len);
        }
    }
}

 

 

 

 

기억하자 메소-드

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

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

 

✅   Map.getOrDefault(Object key, V defaultValue) 

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