[Java]백준 BaekJoon.AC 1967 : 트리의 지름 (dfs, Tree)

 

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

1967번: 트리의 지름

 

 

 

파이썬 다시 시작한지 얼마 안돼 헷갈리기도 했고...

감 잃을까봐 오랜만에 자바를 해봤다.

BufferedReader문장 기억 안나서 너무 당황스러웠다ㅋㅋㅋㅋㅋ(웃다보니 웃을 일이 아님)

심지어 다른 것도 기억이 안나서..(코쓱

IntelliJ로 프로그램 바꾸고 처음한 코딩이라 낯선 것도 있었지만 그새 까먹은건 분명했다..ㅋㅋㅋ;;

그래도 파이썬 할 때도 나왔던 자바 습관은 여전히 나와서 다행이었다 ¿

 

문제가 쉬웠던 건지... 코드 양이 적은 걸 보니 쉬웠던게 맞는 건가...ㅠ

게으름 피우며 풀긴 했지만 수월하게 풀려 당황했던 문제.

그래도 트리 문제 맞춰서 위안이 됐다. 당분간은 번갈아가며 집중해야겠다.

 

 

ArrayList를 이용해 나뭇가지를 만들었고 Dot으로 잔가지를 이어줬다.

모든 노드에서 한번씩 출발하며 깊이 우선 탐색을 진행했다.

도달하면 True로 체크해주고, dfs함수 실행시키고, 큰값인지 비교하고. 이게 전부이다. 늘 이론은 간단하지..!

 

 

 

 

 

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

public class Main {
    static int result = 0;
    static ArrayList<Node>[] tree;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n + 1]; //0행렬은 제외
        visit = new boolean[n+1];

        for(int i=1; i<=n; i++){
            tree[i] = new ArrayList<>();
        }

        for(int i=0; i<n-1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());

            tree[u].add(new Node(d, l));
            tree[d].add(new Node(u, l));
        }

        for(int i=1; i<=n; i++){
            dfs(i, 0);
        }

        System.out.println(result);

    }

    static public void dfs(int start, int dia){
        visit[start] = true;

        for(Node tre : tree[start]){
            int fam = tre.fam;
            int len = tre.len;

            if(!visit[fam]) {
                dfs(fam, dia + len);
                //visit[fam] = false;
            }
        }

        if(result < dia){
            result = dia;
        }

        visit[start] = false;
    }
}

class Node{
    int fam;
    int len;

    Node(int fam, int len){
        this.fam = fam;
        this.len = len;
    }
}