[99클럽 코테 스터디 17일차 TIL] 너구리 구구

 

17일차 문제

링크 : https://www.acmicpc.net/problem/18126
 
 
 
문제 풀이
Node 객체와 인접리스트를 활용해 DFS를 수행하며 가장 멀리 갈 수 있는 값을 Math.max를 통해 업데이트 해주었다.
 
처음에 sum과 answer 값을 int로 선언하여 오답이 나와, long으로 변경해주었다.
 
> 간선의 길이 : 1,000,000 이하 정수
> 노드 개수 : 최대 100,000개
 
=> 최대 거리의 경우 , 1,000,000 * (100,000 -1) = 99,999,000,000 으로 int 범위를 초과하게 됨
* int 범위 : 약 -21억 ~ 21억(2,147,483,647)
 
자료형 범위를 확인하는 습관을 들여야겠다..!

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

public class Main {
    static boolean visited[];
    static ArrayList<Node> arr[];
    static long answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for(int i=0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            long dist = Long.parseLong(st.nextToken());

            arr[s].add(new Node(e, dist));
            arr[e].add(new Node(s, dist));
        }

        // 시작지점이 1이므로
        visited[1] = true;
        DFS(1, 0);

        System.out.println(answer);
    }

    private static void DFS(int num, long sum) {
        answer = Math.max(answer, sum);

        for(Node node : arr[num]) {
            int end = node.end;
            if(!visited[end]) {
                visited[end] = true;
                DFS(end, sum + node.dist);
                visited[end] = false;
            }
        }
    }

    static class Node {
        int end;
        long dist;

        public Node(int e, long dist) {
            this.end = e;
            this.dist = dist;
        }
    }
}