[알고리즘] DFS 문제 풀이

백준 1967

import java.util.*;
import java.io.*;

class Main{
    static boolean[] visited;
    static ArrayList<Node>[] nodes;
    static int n;
    static int max = 0;
    static int maxIdx = 0;
    
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String line;
        
        visited = new boolean[n+1];
        nodes = new ArrayList[n+1];
        
        for(int i=0 ; i<=n ; i++){
            nodes[i] = new ArrayList<>();
        }
        
        while((line = br.readLine()) != null){
            StringTokenizer st = new StringTokenizer(line);
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            nodes[parent].add(new Node(child,weight));
            nodes[child].add(new Node(parent,weight));
        }
        
        visited[1]=true;
        dfs(1,0);
        
        visited = new boolean[n+1];
        visited[maxIdx] = true;
        dfs(maxIdx,0);
        System.out.println(max);
    }
    
    public static void dfs(int idx, int cnt){
        
        //최대 값과 , 그때의 노드 번호 갱신 로직
        if(max < cnt){
            max = cnt;
            maxIdx = idx;
        }
        
        for(Node node : nodes[idx]){
            if(!visited[node.idx]){
                visited[node.idx] = true;
                dfs(node.idx , cnt+node.cnt);
            }
        }
    }
    
}

class Node{
    
    int idx, cnt;
    
    Node(int idx, int cnt){
        this.idx = idx;
        this.cnt = cnt;
    }
}

얻어갈 점:

• 이전의 DFS 구현할 때 인접 행렬을 이용했으나, 이번엔 인접 리스트를 통해 구현했음(성능 상의 이점)
• DFS 사용 이유? 그래프를 다 뒤져서 가장 거리가 먼 두 수를 찾아서 더해주는 문제라서 사용했음
• 노드의 값은 인덱스와 가중치 두 개의 속성이 있으니 Class로 묶어줬음
• 더 이상 입력이 없을때까지 조건 => String line, (line.readLine()) != null로 표현
• 인접 행렬로 구현시에도 1,2에 값이 1이 세팅되면 2,1에도 해줘야하듯이 인접 리스트도 동일하게 양방향으로 매칭해줘야함
• 1차로 dfs를 1번 노드 기준으로 돌리면 가장 거리가 먼 노드를 찾음(이때의 max값은 가장 큰 노드의 번호와 그 때의 가중치)
• max값을 기준으로 dfs를 한 번 더 돌리면 1차로 찾은 가장 거리가 먼 노드에서 또 제일 먼 노드 찾기 가능 => 최대값!