[백준] 1967번 트리의 지름 JAVA (자바) 풀이

문제 1967번 (dfs)

 

 :  트리(tree)는 사이클이 없는 무방향 그래프

    트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재

    어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것

 :  이런 두 노드 사이의 경로의 길이를 트리의 지름

    입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해라

 

 :  아래와 같은 트리가 주어진다면 트리의 지름은 45

 

 

 

 [입력]

 :  파일의 첫 번째 줄은 노드의 개수 n (1 ≤ n ≤ 10,000)

 :  둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보 (세 개의 정수)

    (연결하는 두 노드 중 부모 노드의 번호, 자식 노드, 간선의 가중치)

    간선에 대한 정보는 부모 노드의 번호가 작은 순, 부모 같다면 자식노드 작은 순

    루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수

 

 

 [출력]

 :  첫째 줄에 트리의 지름을 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs 

 

 

 1. 트리 같이 하나의 노드의 다중연결은 리스트로!

• ArrayList 사용
• for(int t:tree[node]) 사용해서 순회

 

 2. dfs 실행 전 visit 초기화

• 깊은 dfs를 통해 거리합을 모두 완성하므로 for문을 나와 새로운 dfs를 시작할 때 visit 함수도 초기화 한다<' 일 경우) 현지점 < 다음지점
  
  

 3. NullPointer 에러 주의

• 입력은 N개가 아니라 N-1만큼 받기 때문에 for문의 범위를 잘 보아야한다                

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N;
    static int max = 0;
    static boolean visit[];
    static ArrayList<int []> tree[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[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 p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            tree[p].add(new int[]{c,w});
            tree[c].add(new int[]{p,w});
        }
        
        for(int i=1;i<tree.length;i++){
            visit = new boolean[N+1];
            dfs(i,0);
        }
        System.out.println(max);
    }
    
    static void dfs(int node, int distance){
        visit[node] = true;
        max = Math.max(distance,max);
        
        for(int[] t:tree[node]){
            if(!visit[t[0]]){
                dfs(t[0], distance+t[1]);
            }
        }
    }
}

 

 [해설]
     

 :  static int N;  
    static int max = 0;
    static boolean visit[];
    static ArrayList<int []> tree[];

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  첫째줄 입력
    tree = new ArrayList[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 p = Integer.parseInt(st.nextToken());  부모 노드
            int c = Integer.parseInt(st.nextToken());  자식 노드
            int w = Integer.parseInt(st.nextToken());  가중치
            
            tree[p].add(new int[]{c,w});  자식과 가중치 저장
            tree[c].add(new int[]{p,w});  부모와 가중치 저장
    }
        
 :  for(int i=1;i<tree.length;i++){  i 노드와 연결된 다른 노드 검사
            visit = new boolean[N+1];  dfs 전 방문 초기화
            dfs(i,0);  dfs 실행
    }

 :  System.out.println(max);  결과출력
    
    
 :  static void dfs(int node, int distance){  현재노드, 거리합
        visit[node] = true;
        max = Math.max(distance,max);  max가 되는 거리 찾아내기
        
        for(int[] t:tree[node]){  현재 노드와 연결된 다른 노드들 검사
            if(!visit[t[0]]){  방문 전이라면
                dfs(t[0], distance+t[1]);  연결된 다음 노드, 거리합 추가
            }
        }
    }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *