[JAVA]BOJ 1967, 트리의 지름

어렵다.. 골드였구나

 

1. 트리를 만든다.

2. dfs를 두 번 진행한다.

 

이렇게만 보면 간단해보이는데.. 구현하는게 어려웠다.

 

1. 트리를 만든다.

ArrayList<Node>[] tree; // 선언

// 트리 초기화
tree = new ArrayList[n + 1];
for(i=0;i<=n;i++) // 1번 노트부터 사용하지만 null포인터 에러나서 [0]도 초기화함
    tree[i] = new ArrayList<>();

// 트리 만들기 -> 간선개수는 노드개수 -1
for(i=1;i<n;i++) {
    st = new StringTokenizer(br.readLine());
    parent = Integer.parseInt(st.nextToken());
    child = Integer.parseInt(st.nextToken());
    weight = Integer.parseInt(st.nextToken());
    // 부모-자식 사이 간선 추가
    tree[parent].add(new Node(child, weight));
    tree[child].add(new Node(parent, weight));
}

 

이번 문제는 ArrayList로 트리를 구현한다. 트리를 초기화할때 i=1부터 했더니 자꾸 NullPointer가 발생해서 i=0으로 바꿨다. 바꿨더니 에러가 안나고 정답을 맞췄다.

ArrayList에 tree[부모]에  '부모, 자식, 간선가중치'를 저장한다. 그리고 부모-자식이 연결됐다는건 자식-부모도 연결되어있다는 뜻이므로 tree[자식]에 '자식, 부모, 간선가중치'를 저장한다.

예를 들어 3 , 1 2 3, 1 3 5 라면 tree[1]에는 1과 2가 3의 거리이고 1과 3이 5의 거리인게 저장될것이다. 그리고 tree[2]에는 2와 1이 3의 거리인게 저장된다. tree[3]에는 3과 1이 5의 거리인게 저장된다.

 

2. dfs 메소드와 main에서 dfs호출

public class Node {
    int vertex, weight;

    public Node(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}

위는 노드 클래스이다.

public static void dfs(ArrayList<Node>[] tree, int node, int dist, int[] maxDist, int[] fatrhestNode, boolean[] visited){
    visited[node] = true;

    if(dist > maxDist[0]){ // 현재까지 거리가 제일 긴 거리보다 길때 바꿔줘야함
        maxDist[0] = dist;
        fatrhestNode[0] = node;
    }

    for(Node next : tree[node]){
        if(!visited[next.vertex]) // 방문되지 않았을때만 진행
            dfs(tree, next.vertex, dist + next.weight, maxDist, fatrhestNode, visited); // 다음 노드로 넘어간 만큼 가중치를 더해 재귀
    }
}

 

// 총 2번의 DFS 실행
// 1번째 DFS
visited = new boolean[n + 1];
dfs(tree, 1, 0, maxDist, farthestNode, visited);

// 2번째 DFS
maxDist[0] = 0;  // 거리 다시 초기화
visited = new boolean[n + 1];
dfs(tree, farthestNode[0], 0, maxDist, farthestNode, visited);

System.out.println(maxDist[0]);

제일 긴 지름을 구하기 위해서는.. 두 번의 dfs를 진행한다. 

첫번째에 임의의 지점에서 제일 먼 노드를 찾는다.(보통 루트에서 시작함) 두번째에 첫번째 dfs에서 찾은 제일 먼 노드에서 제일 먼 노드2를 찾는다.

그때의 거리(가중치)를 출력한다.

 

보통 전역변수를 많이 쓰는데.. 나는 C언어로 코딩을 처음 배워서 전역변수보다는 포인터에 익숙해 전역변수를 쓰지 않았다. 근데 자바에는 포인터가 없으니까... 고민하다가 그냥 1칸짜리 배열을 만들어서 매개변수로 사용했다.

 

생각해내는 것도 어렵고, 구현하는 것도 어렵지만 하나씩 차근차근 보고 이해하면 완성할 수 있다.

---

아래는 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ1967 {
    public static void dfs(ArrayList<Node>[] tree, int node, int dist, int[] maxDist, int[] fatrhestNode, boolean[] visited){
        visited[node] = true;

        if(dist > maxDist[0]){
            maxDist[0] = dist;
            fatrhestNode[0] = node;
        }

        for(Node next : tree[node]){
            if(!visited[next.vertex])
                dfs(tree, next.vertex, dist + next.weight, maxDist, fatrhestNode, visited);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Node>[] tree;
        StringTokenizer st;
        boolean[] visited;
        int n, i, parent, child, weight;
        int [] farthestNode = {0};
        int [] maxDist = {0};

        n = Integer.parseInt(br.readLine());

        // 트리 초기화
        tree = new ArrayList[n + 1];
        for (i = 0; i <= n; i++) { // 1번 노트부터 사용하지만 null포인터 에러나서 [0]도 초기화함
            tree[i] = new ArrayList<>();
        }

        // 트리 만들기 -> 간선개수는 노드개수 -1
        for(i=1;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            parent = Integer.parseInt(st.nextToken());
            child = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());
            // 부모-자식 사이 간선 추가
            tree[parent].add(new Node(child, weight));
            tree[child].add(new Node(parent, weight));
        }

        // 총 2번의 DFS 실행
        // 1번째 DFS
        visited = new boolean[n + 1];
        dfs(tree, 1, 0, maxDist, farthestNode, visited);

        // 2번째 DFS
        maxDist[0] = 0;  // 거리 다시 초기화
        visited = new boolean[n + 1];
        dfs(tree, farthestNode[0], 0, maxDist, farthestNode, visited);

        System.out.println(maxDist[0]);
    }
}

public class Node {
    int vertex, weight;

    public Node(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}