공부 206일차: 백준 1167번 트리의 지름 자바 java

1167 트리의 지름

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

1167번: 트리의 지름

 

 

 

 

---

백준 1167번 문제 트리의 지름

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	37981	13784	9877	33.828%

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

제한

 

예제 입력 1

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

예제 출력 1

11

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

오답부터..~

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int v, node;
    static int max = Integer.MIN_VALUE;
    static ArrayList<ArrayList<Node>> tree = new ArrayList<>();
    static boolean[] visited;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        v = Integer.parseInt(br.readLine());
        visited = new boolean[v+1];
        
        for(int i = 0; i < v+1; i++) {    // 숫자 그대로 쓰려고
            tree.add(new ArrayList<>());
        }
        
        for(int i = 0; i < v; i++) {
            st = new StringTokenizer(br.readLine());
            int point = Integer.parseInt(st.nextToken());
            
            while(true) {
                int linkedP = Integer.parseInt(st.nextToken());
                if(linkedP == -1) {
                    break;
                }
                int distance = Integer.parseInt(st.nextToken());
                tree.get(point).add(new Node(linkedP, distance));
            }
        }
        
        dfs(1, 0);
        bw.write(max+"");
        bw.flush();
        bw.close();
        br.close();
    }
    
    static void dfs(int x, int distance) {
        visited[x] = true;    // 방문 처리
 
        for(Node n : tree.get(x)) {    // 연결된 노드들 전부 탐색
            if(!visited[n.x]) {
                max = Math.max(max, n.distance+distance);
                dfs(n.x, n.distance+distance);
            }
        }
    }
 
    static class Node{
        int x;
        int distance;
        Node(int x, int distance){
            this.x = x;
            this.distance = distance;
        }
    }
}
 

 

지금까지 클래스 만들어서 푼 문제들처럼 적고 예제 입력을 넣으니 예제 출력이랑 똑같이 11이 뜨길 이렇게 간단한 문젠가..? 싶어서 제출해봤지만 역시나 오답

 

이후 이 영상을 보면서 참고했다

핵심은 어느 노드에서 출발했든 dfs나 bfs를 돌렸을 때 가장 멀리 있는 노드는 트리의 지름을 구성하는 2개의 노드 중 하나이다

 

그래서 아무데서나 dfs 혹은 bfs를 돌려서 지름 노드 하나를 찾은 후, 그 지름 노드에서 가장 먼 노드, 즉 또다른 지름 노드를 구하면 된다

 

dfs 혹은 bfs를 2번 돌려야 한다는 것!

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int v, node;
    static int max = Integer.MIN_VALUE;
    static ArrayList<ArrayList<Node>> tree = new ArrayList<>();
    static boolean[] visited;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        v = Integer.parseInt(br.readLine());
        visited = new boolean[v+1];
        
        for(int i = 0; i < v+1; i++) {    // 숫자 그대로 쓰려고
            tree.add(new ArrayList<>());
        }
        
        for(int i = 0; i < v; i++) {
            st = new StringTokenizer(br.readLine());
            int point = Integer.parseInt(st.nextToken());
            
            while(true) {
                int linkedP = Integer.parseInt(st.nextToken());
                if(linkedP == -1) {
                    break;
                }
                int distance = Integer.parseInt(st.nextToken());
                tree.get(point).add(new Node(linkedP, distance));
            }
        }
        
        dfs(1, 0);
        visited = new boolean[v+1];    // 한 번 더 돌려야하므로 방문 기록 초기화
        dfs(node, 0);
        bw.write(max+"");
        bw.flush();
        bw.close();
        br.close();
    }
    
    static void dfs(int x, int distance) {
        visited[x] = true;    // 방문 처리
 
        for(Node n : tree.get(x)) {    // 연결된 노드들 전부 탐색
            if(!visited[n.x]) {
                if(n.distance+distance > max) {
                    node = n.x;        // 최장길이 노드 저장
                    max = n.distance+distance;    // 최장길이 저장
                }
                dfs(n.x, n.distance+distance);
            }
        }
    }
 
    static class Node{
        int x;
        int distance;
        Node(int x, int distance){
            this.x = x;
            this.distance = distance;
        }
    }
}
 

 

 

 

---

처음 오답을 도출해내기까지 되게 오래 잡고 있었는데.. 왜 그랬는지... 모르겠다..