[BOJ - JAVA] 1967 - 트리의 지름 (DFS)

# 주소

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

1967번: 트리의 지름

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
public class Main{
    static int n, m;
    static ArrayList<Node> list[];
    static boolean[] visit;
    static int max = 0;
    static int max_idx = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        list = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 0; i < n-1; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
        }
        visit = new boolean[n+1];
        visit[1] = true;
        dfs(1,0);

        visit = new boolean[n+1];
        visit[max_idx] = true;
        dfs(max_idx,0);
        System.out.println(max);
    }
    public static void dfs(int idx, int cnt){
        if(max < cnt){
            max = cnt;
            max_idx = idx;
        }
        for (Node a : list[idx]) {
            if(!visit[a.idx]){
                visit[a.idx] = true;
                dfs(a.idx, cnt + a.cnt);
            }
        }
    }
}
class Node{
    int idx, cnt;
    Node(int idx, int cnt){
        this.idx = idx;
        this.cnt = cnt;
    }
}

이걸 배열로 풀면 터집니다.

그래서 양방향 배열인 ArrayList를 이용하여 크기가 있는 list로 입력을 받습니다.

그러므로 일반 ArrayList와는 다르게, list의 크기를 n+1로 선언합니다.

list = new ArrayList[n+1];

그리고 해당 list의 세로 크기를 다 지정했으면, 각 list[i]에 대하여 ArrayList<>를 선언해야 list를 이용할 수 있습니다.

따라서 n 크기가 12이므로 list[i] = ArrayList<>();라고 선언합니다.

 

이후 for문을 이용해 Input값을 a, b, c로 입력 받아 각각을 list에 넣을 것인데요.

a는 부모노드, b는 자식 노드, c는 가중치라고 했을 때 하나의 Input값이라면 list에 두 가지를 넣어야 합니다.

왜냐하면, 우리 2차원 배열로 dfs, bfs문제 풀 때 arr[1][3]과 arr[3][1]을 둘 다 1로 넣었던거 기억하시나요?

list를 이용하여 풀 때에도 2차원으로 풀기 위해, list[a]에는 new Node인 (b, c)를 넣고 반대로 list[b]에도 (a, c)를 삽입합니다.

 

이렇게 해야, list[a]만 보고 가장 멀리 있는 노드를 찾으려고 할 때 다시 돌아올 수 있습니다.

그리고 밑을 보시면 visit을 두 개 선언했습니다.

첫 뻔재 문단을 살펴보면

        visit = new boolean[n+1];
        visit[1] = true;
        dfs(1,0);

visit을 선언하고 visit[1] = true로 지정합니다.

이는 dfs를 1부터 돌릴 것이기 때문에 1의 위치는 방문한 곳이어야 하기 때문입니다.

근데 꼭 알아야 할 것이 있는데, 바로 위에서 언급했던 visit을 그 밑에

visit = new boolean[n+1];
        visit[max_idx] = true;
        dfs(max_idx, 0);
        System.out.println(max);

이렇게 선언하는 이유는, 각각의 dfs문이 가지는 의미가 다르기 때문입니다.

첫 번째 dfs문의 역할은 루트노드인 1 입장에서 가장 멀리 있는 노드를 찾는 것이 목표입니다.

그래서 그 노드를 찾으면, 두 번째 dfs문을 가동할 것인데 이를 위해 visit 을 새로 선언하고 1입장에서 가장 멀리 있는 노드를 max_idx로 지정한 뒤 visit[max_idx] = true로 바꾸는 것입니다.

그리고 dfs(max_idx , 0)을 실행합니다.

그럼 이 dfs문을 어떻게 짤 수 있을까요?

public static void dfs(int idx, int cnt){
        if(max < cnt){
            max = cnt;
            max_idx = idx;
        }
        for(Node a : list[idx]){
            if (!visit[a.idx]) {
                visit[a.idx] = true;
                dfs(a.idx, cnt + a.cnt);
            }
        }
    }

dfs에 들어가는 인자는 idx, cnt로 들어가는데, idx는 인덱스, cnt는 가중치를 의미합니다.

따라서 제일 처음 dfs(1,0)이 실행될 때 if문은 건너뛰게 되고 for문 부터 실행합니다.

이 때 list[1]을 전부 돌리는데, list[1]에는 2와 3을 자식 노드로 가지고 있습니다.

그러므로 dfs에는 dfs(2, cnt + 2의 cnt) 와 dfs(3, cnt + 3의 cnt)를 둘 다 실행합니다.

이러면서 루트 노드인 1입장에서 어디가 제일 멀지 가중치를 구할텐데요.

이 구문은 if문을 통해 손쉽게 구할 수 있습니다.

if(max < cnt){
            max = cnt;
            max_idx = idx;
        }

여기서 max는 cnt로, max_idx는 idx를 넣어서 계속해서 가중치와 max를 갱신할 수 있습니다.

이로 인해 첫 번째 dfs문을 실행한 결과 루트노드인 1에서 가장 멀리 있는 노드를 찾을 수 있습니다.

그리고 그렇게 구해진 노드의 위치를 max_idx에 담아서 dfs(max_idx, 0)을 실행하면 분명 max와 max_idx가 또 구해집니다.

여기서 구해진 max와 max_idx 중 가중치인 cnt가 최종적인 정답이 됩니다.

 

요약하자면, 이 문제를 풀기 위해서 전 모든 노드에 대해서 각 경우의 수의 노드를 탐색하여 가장 멀리 있는 노드로 가야할까.. 생각을 했었습니다.

근데 쉽게 생각해보면 루트 노드인 1입장에서 가장 멀리 있는 노드를 찾고 그 노드와 가장 멀리 떨어진 노드가 최종적으로 제일 멀리 떨어져 있는 (가중치가 max)인 노드가 됩니다.

감사합니다.