너구리 구구 - 18126

문제

풀이

package Baekjoon;


import java.util.ArrayList;
import java.util.Scanner;

// 너구리 구구 - DFS
// 그냥 끝으로 가면된다.
// 인접리스트를 이용한 경로 탐색 문제. 기본이면서 매우 중요한 문제.
class Edge{
    int y;
    int dis;
    public Edge(int y,int dis){
        this.y = y;
        this.dis = dis;
    }
}
public class ex18126 {
    static ArrayList<ArrayList<Edge>> graph;
    static boolean[] ch;
    static int n;
    static long answer=0;

    public static void DFS(int now,long dis){
        if(answer<dis){
            answer = dis;
        }

        for(Edge edge : graph.get(now)){
            if(ch[edge.y]) continue;
            else{
                ch[edge.y] = true;
                DFS(edge.y, dis+ edge.dis);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        ch = new boolean[n+1];
        graph=new ArrayList<ArrayList<Edge>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Edge>());
        }

        for(int i=1; i<=n-1; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int dis = sc.nextInt();

            //양방향 그래프.
            graph.get(x).add(new Edge(y,dis));
            graph.get(y).add(new Edge(x,dis));
        }

        ch[1] = true;
        DFS(1,0);
        System.out.println(answer);
    }

}

인접리스트를 이용한 경로를 탐색하고 끝으로가는 거리를 구하면된다. 단순한 문제이면서, 인접리스트 DFS의 기본이자 핵심 문제이다. 이 유형을 문제를 오랜만에 풀었는데, 헷갈렸다. 연습하자. ........

DFS은 크게 기본 미로탐색같은 템플릿구조를 띄는 문제와 인접리스트 인접행렬을 이용한 그래프 형태의 DFS문제 2가지로 나뉜다.

그래프 형태에 소홀해졌다. 연습을 하자. 무방향,양방향그래프도 신경쓰자.