Java 백준 문제풀이 (55) 1167_트리의 지름

한동안 티스토리 서버가 날아간 덕분에 문제 풀고 풀이를 못 올렸는데

정말 문제 푼 것 같지가 않았다.. ㅎ

 

오늘의 문제는 트리의 지름이다.

문제를 읽자마자 작성한 나의 주석을 먼저 보자.

 

        // 트리의 지름 ?
        // 루트에서 가장 먼 노드 n1 <-> n1과 가장 멀리 있는 노드 n2의 거리.
        // 가중치와 에지 정보가 모두 필요하므로 별도의 Node 클래스가 필요하다.
        // bfs dfs? dfs를 이상하게 구현하지 않는 이상 큰 의미 없을 듯..? 어차피 완전탐색해야함.
        // 다만 깊이가 깊어질수록 dfs가 불리해서 굳이 선택하면 bfs가 무난한데 난 dfs가 좋 - 아
        // 가장 먼 노드 + 그놈하고 제일 먼 노드 => 두 번 탐색 필요
 
        // 근데 노드가 1번부터 시작하는 건지 0번부터인지 기재되어 있지 않음.. 뭐지
        // 예제는 1번부터니 일단 1번으로 시작
 
        // 1번째 입력값 노드 개수 V
        // 2번째 입력값 노드 번호 N, 에지 정보 V, -1이 나오면 다음 노드로

 

문제 자체가 어렵진 않았는데 생각보다 고민할 게 많았다.

어떤 변수가 필요한지 등등..

 

 

1. 일단 트리의 지름은 (루트에서 가장 먼 노드)로부터 가장 멀리 있는 노드이다.

몰랐으면 지금부터 알면 된다. 나도 전에 다른 문제 풀면서 알았다.

 

2. 가중치가 들어가는 문제의 경우 클래스를 만들어서 푸는 게 일반적이다. 물론 다른 방법도 있다.

 

3. 완전 탐색으로 가장 깊은 노드를 찾아야 하는데, 아무래도 dfs는 깊이가 깊어질수록 불리하므로 bfs가 무난하긴 하다.

근데 난 dfs가 좋으므로 비합리적인 선택을 할 것이다. 틀리면 다시 풀면 되지.

 

4. 노드가 몇 번부터 시작하는지 모르겠는데 예제에서는 1번부터 시작함. 일단 그걸 기준으로 배열을 만들기로 했다.

 

 

 

이런 전제 조건을 바탕으로 야매 수도코드를 작성해봤다.

 

 

public class Main {
    // 가장 멀리 있는 노드 기록할 변수 생성 -> 초기화 필요 없음
    public static int max_node;
    // max 가중치 기록할 변수 생성 -> 초기화 필요 없음
    public static int max_weight;
    public static final int START_NODE = 1;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 트리의 지름 ?
        // 루트에서 가장 먼 노드 n1 <-> n1과 가장 멀리 있는 노드 n2의 거리.
        // 가중치와 에지 정보가 모두 필요하므로 별도의 Node 클래스가 필요하다.
        // bfs dfs? dfs를 이상하게 구현하지 않는 이상 큰 의미 없을 듯..? 어차피 완전탐색해야함.
        // 다만 깊이가 깊어질수록 dfs가 불리해서 굳이 선택하면 bfs가 무난한데 난 dfs가 좋 - 아
        // 가장 먼 노드 + 그놈하고 제일 먼 노드 => 두 번 탐색 필요
 
        // 근데 노드가 1번부터 시작하는 건지 0번부터인지 기재되어 있지 않음.. 뭐지
        // 예제는 1번부터니 일단 1번으로 시작
 
        // 1번째 입력값 노드 개수 V
        // 2번째 입력값 노드 번호 N, 에지 정보 V, -1이 나오면 다음 노드로
 
        // 노드 개수 V 받기
 
        // 노드개수 V+1 만큼의 ArrayList<Node>를 인자로 가지는 배열 lists 생성
 
        // 2중 반복문
            // 1차 (lists.length만큼)
            // lists[i] = new ArrayList<Node>;
            // 2번째 입력값 받아서 split or StringTokenizer
                // 2차 for(2번째 입력값 배열 길이만큼, +2씩 증가)
                // 0번은 노드 번호이므로 1번부터
                // 첫번째 입력값이 -1? break
                // 아니라면 lists[j]
                // lists[j+1] = .. 퐁당퐁당 넣기
                // lists[i].add (new Node (j , j+1));
 
        // 방문 여부 기록용 변수 생성(+1)
        // 가중치용 변수 (무의미함)
        // dfs(현재 노드, 배열, 방문용 배열, 가중치)
 
        // 방문 여부 초기화
 
        // dfs(max node, 배열, 방문용 배열, 가중치)
 
        // 출력 최대 가중치
    }
 
    // dfs(현재 노드, 방문용 배열, 배열, 가중치)
        // 방문했다면 리턴
 
        // 만약 최대 가중치보다 지금 가중치가 더 크다면?
        // 최대 가중치 = 현재 가중치
        // 최대 가중치 노드 = 현재 노드
 
        // 반복문
        // 배열[노드]의 길이만큼 돌면
            // if (방문 안함)
 
                // dfs(현재 노드, 방문용 배열, 배열, 가중치 + 다음 노드의 가중치)
 
    }
}
 
// 노드 클래스
class Node {
    // 가중치
    int weight;
    // 에지 정보
    int edge;
    // 생성자
    public Node (int weight, int edge) {
        this.weight = weight;
        this.edge = edge;
    }
}
 

 

사실 가중치나 가중치를 가진 노드를 저장하는 것도 정적 변수가 아니라 배열을 만들어서 해도 되지만

작성하다보니 인자가 너무 많아지는 것 같아서 실수할 확률을 줄이기 위해서 밖으로 빼버렸다

만약 코테가 면접까지 이어진다면 생각하면 최대한 정적 변수는 배제하는 게 좋을 것 같긴 하다

 

근데 틀리면 의미 없으니 실수 많이 하는 사람은 정적 변수라도 쓰자

 

max_node나 max_weigth같은 경우는 무조건 두 번째가 더 빠르기 때문에 굳이 초기화해줄 필요 없음.

그리고 위에서 말했던 것처럼 dfs는 두 번 반복할 것이다.

 

그리고 늘 그렇듯 틀렸다

근데 거의 정답에 근접한 상태라서 더이상 설명하면 그냥 정답이 나오니까 직접 풀어보자

 

힌트 = 문제에서 제시해주는 값 중 하나가 별 의미 없어보인다? -> 무조건 뭔가 잘못 생각하고 있는 것

늘 알면서도 같은 실수를 반복하지..

 

정답은 아래에

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
    // 가장 멀리 있는 노드 기록할 변수 생성 -> 초기화 필요 없음
    public static int max_node;
    // max 가중치 기록할 변수 생성 -> 초기화 필요 없음
    public static int max_weight;
    public static final int START_NODE = 1;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 트리의 지름 ?
        // 루트에서 가장 먼 노드 n1 <-> n1과 가장 멀리 있는 노드 n2의 거리.
        // 가중치와 에지 정보가 모두 필요하므로 별도의 Node 클래스가 필요하다.
        // bfs dfs? dfs를 이상하게 구현하지 않는 이상 큰 의미 없을 듯..? 어차피 완전탐색해야함.
        // 다만 깊이가 깊어질수록 dfs가 불리해서 굳이 선택하면 bfs가 무난한데 난 dfs가 좋 - 아
        // 가장 먼 노드 + 그놈하고 제일 먼 노드 => 두 번 탐색 필요
 
        // 근데 노드가 1번부터 시작하는 건지 0번부터인지 기재되어 있지 않음.. 뭐지
        // 예제는 1번부터니 일단 1번으로 시작
 
        // 1번째 입력값 노드 개수 V
        // 2번째 입력값 노드 번호 N, 에지 정보 V, -1이 나오면 다음 노드로
 
        // 노드 개수 V 받기
        int V = Integer.parseInt(br.readLine());
 
        // 노드개수 V+1 만큼의 ArrayList<Node>를 인자로 가지는 배열 lists 생성
        ArrayList<Node>[] lists = new ArrayList[V+1];
 
        // 2중 반복문
        for (int i=START_NODE; i<lists.length; i++) {
            // 1차 (lists.length만큼)
            // lists[i] = new ArrayList<Node>;
            String[] input = br.readLine().split(" ");
            // 2번째 입력값 받아서 split or StringTokenizer
            int node = Integer.parseInt(input[0]);
            lists[node] = new ArrayList<>();
            for (int j=1; j< input.length; j+=2) {
                // 2차 for(2번째 입력값 배열 길이만큼, +2씩 증가)
                // 0번은 노드 번호이므로 1번부터
                int input1 = Integer.parseInt(input[j]); // 노드
                // 첫번째 입력값이 -1? break
                if (input1 == -1) break;
                // 아니라면 lists[j]
                int input2 = Integer.parseInt(input[j+1]); // 가중치
                // lists[j+1] = .. 퐁당퐁당 넣기
                // lists[i].add (new Node (j , j+1));
                lists[node].add(new Node(input2,input1));
            }
        }
 
        // 방문 여부 기록용 변수 생성(+1)
        boolean[] visited = new boolean[V+1];
        // 가중치용 변수 (무의미함)
        int weight = 0;
        // dfs(현재 노드, 배열, 방문용 배열, 가중치)
        dfs(START_NODE, visited,lists,  weight);
 
        // 방문 여부 초기화
        visited = new boolean[V+1];
 
        // dfs(max node, 배열, 방문용 배열, 가중치)
        dfs(max_node, visited, lists, weight);
 
        // 출력 최대 가중치
        System.out.println(max_weight);
    }
 
    // dfs(현재 노드, 방문용 배열, 배열, 가중치)
    public static void dfs(int node, boolean[] visited, ArrayList<Node>[] lists, int weight) {
        // 방문했다면 리턴
        if (visited[node]) return;
 
        // 만약 최대 가중치보다 지금 가중치가 더 크다면?
        // 최대 가중치 = 현재 가중치
        // 최대 가중치 노드 = 현재 노드
        if (max_weight < weight) {
            max_weight = weight;
            max_node = node;
        }
 
        visited[node] = true;
        // 반복문
        // 배열[노드]의 길이만큼 돌면서
        for (int i=0; i<lists[node].size(); i++) {
            // if (방문 안함)
            Node next = lists[node].get(i);
            if (!visited[next.edge]) {
                // dfs(현재 노드, 방문용 배열, 배열, 가중치 + 다음 노드의 가중치)
                dfs(next.edge, visited, lists, weight + next.weight);
            }
        }
    }
}
 
// 노드 클래스
class Node {
    // 가중치
    int weight;
    // 에지 정보
    int edge;
    // 생성자
    public Node (int weight, int edge) {
        this.weight = weight;
        this.edge = edge;
    }
}
 

 

 

주석은 처음 작성하고 수정하지 않으니 신경쓰지 말자