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

🔺 문제

1167번: 트리의 지름

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static ArrayList<Node>[] A;   // 그래프 데이터 저장 인접 리스트
    static boolean[] visited;    // 방문 배열
    
    static int[] dp;    // 거리 저장 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int V = Integer.parseInt(br.readLine());
        
        A = new ArrayList[V + 1];
        for(int i = 1 ; i <= V ; i++) {
            A[i] = new ArrayList<Node>();
        }
        
        // 🎈 자유자재 입력 받기
        for(int i = 1 ; i <= V ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            
            while(true) {
                int e = Integer.parseInt(st.nextToken());
                if(e == -1) break;
                
                int v = Integer.parseInt(st.nextToken());
 
                A[s].add(new Node(e, v));
            }
        }
 
        
        visited = new boolean[V + 1];
        dp = new int[V + 1];
        bfs(1);
        
 
        // 🔔 dp 배열에서 가장 큰 값으로 다시 시작점 설정 🔔
        int max = 1;
        for(int i = 2 ; i <= V ; i++) {
            if(dp[max] < dp[i]) {
                max = i;
            }
        }
        
        visited = new boolean[V + 1];
        dp = new int[V + 1];
        bfs(max);    // 🔔 새로운 시작점으로 설정
        
       Arrays.sort(dp); // 🔔 정렬을 해줘야함,,,
       System.out.println(dp[V]);
        
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        visited[num] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(Node next : A[now]) {
                if(!visited[next.idx]) {
                    visited[next.idx] = true;
                    queue.add(next.idx);
                    dp[next.idx] = dp[now] + next.val;    // 🔔 노드 거리 배열 업데이트 (현재 노드 거리 + 엣지 가중치)
                }
            }
        }
    }
}
 
class Node {
    int idx;    // 목적지 노드
    int val;    // 엣지 가중치
    
    Node(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
}

✅ 해결 아이디어
- BFS / DFS (가장 긴 경로 찾기)
→ 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드 = 트리의 지름에 해당하는 두 노드 중 하나
1) 한 정점에서 가장 멀리 있는 정점 찾기
2) 그 정점에서 가장 멀리 있는 정점 찾기
=> 총 두 번 수행하면 됨.

 

 

---

🔺 다른 풀이들

인터넷에는 DFS를 활용한 풀이가 더 많다...

 

[백준]1167: 트리의 지름 - JAVA

DFS를 활용하셨다... 설명이 아주 굿...

 

[백준] 1167 : 트리의 지름 (JAVA/자바)

[java 백준] 골드 3/ 1167번 트리의 지름

 

- 개쩐다!!!! 이거다.

로그인

---

💬 느낀 점

후엥 어렵구나,,,,ㅠㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	6/15

 

(+ 6/15 2회독)

코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int V;
    static ArrayList<Node>[] A;
    static boolean[] visited;
 
    static int[] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        V = Integer.parseInt(br.readLine());
        
        A = new ArrayList[V + 1];
        for(int i = 1 ; i <= V ; i++) {
            A[i] = new ArrayList<Node>();
        }
        
        for(int i = 1 ; i <= V ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            
            while(true) {
                int e = Integer.parseInt(st.nextToken());
                if(e == -1) break;
                
                int v = Integer.parseInt(st.nextToken());
                A[s].add(new Node(e, v));
            }
        }
        
        visited = new boolean[V + 1];
        dp = new int[V + 1];
        bfs(1);
        
        int max = 1;
        for(int i = 2 ; i <= V ; i++) {
            if(dp[max] < dp[i]) {
                max = i;
            }
        }
        
        visited = new boolean[V + 1];
        dp = new int[V + 1];
        bfs(max);
        
        Arrays.sort(dp);
        System.out.println(dp[V]);
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        visited[num] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(Node next : A[now]) {
                if(!visited[next.idx]) {
                    visited[next.idx] = true;
                    queue.add(next.idx);
                    dp[next.idx] = dp[now] + next.val;
                }
            }
        }
    }
}
 
class Node {
    int idx;
    int val;
    
    Node(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
}

와 진짜 푼지 얼마 안된것 같은데 벌써 두 달 지나서 복습하는 거였네

시간 넘 빠르다..

 

암튼 문제 감은 잡았고 놓친 부분은 아래와 같다.

 

1) 저 자유자재로 입력받는 거

2) dp 배열에서 가장 큰 값으로 다시 시작점 설정하고 bfs(max)하는 거

3) 거리 값 업데이트 →  dp

    → 여기서 dp를 썼었구나 싶다 그 때는 dp 모르고 푼 문제라 이게 dp 쓴 건지도 몰랐는디

 

암튼... 담엔 혼자 풀 수 있음 좋겠다!