[백준 1167] 트리의 지름 (JAVA)

백준 1167번 문제  - 트리의 지름

1167번: 트리의 지름

---

문제 분석

 

• 정점을 입력 받는다
  • 어떤 정점의 간선을 입력 받을 지 먼저 입력 | 간선으로 이어질 정점 | 간선까지의 거리를 입력 | (반복) | -1
  • 1 3 2 -1
• 입력받은 정점들 간의 거리 중 가장 긴 거리를 출력해라

---

해결 키 포인트

 

• DFS(깊이 우선 탐색) 개념 파악
• 정점의 간선을 순서대로 입력 받는게 아니라, 맨 앞에 정점을 선언하여 불규칙적으로 입력 받을 수 있다
  • ex) 2 4 4 -1
           1 3 2 -1
• 가장 긴 거리를 알기 위해, 긴 거리의 두 정점 중 한 정점이라도 알아내야 한다
  • 어떻게? 아무 정점을 시작점으로 두고 DFS, 이때 가장 긴거리로 측정되는 끝 정점을 기억해둔다
  • 가장 긴거리로 측정되는 끝 정점을 어떻게 기억하나? (필자는 이를 못해 어려움을 겪음)
    현재 노드가 마지막 노드인지 확인(더 이상 뒤에 노드가 없는지) | 현재 노드까지의 distance가 가장 긴 거리와 동일한지 확인

---

깊이 우선 탐색(DFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

 

깊이 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 후입 선출 특성을 가짐 ( 재귀함수 사용 많음 / 스택도 사용 )

 

알고리즘

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

Do It! 알고리즘 코딩 테스트

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 (이를 모든 정점을 다한다)

 

Do It! 알고리즘 코딩 테스트

 

만약 스택에 노드가 없으면, 방문하지 않은 정점을 알아내, 스택에 삽입하고 다시 2번 단계를 반복한다.

---

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static int maxDistance = 0;
    public static int maxNodeLastIndex = 0;
    public static boolean[] isChecked;

    public static ArrayList<Node>[] lists;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // V 입력
        int V = Integer.parseInt(br.readLine());

        // 큐 및 체크 리스트 생성
        lists = new ArrayList[V];
        isChecked = new boolean[V];

        // 각 V에 연결된 정보 입력
        for (int i = 0; i < V; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int index = Integer.parseInt(st.nextToken()) - 1;

            // 큐 생성
            lists[index] = new ArrayList<>();

            // 연결된 정점 추가
            int count = st.countTokens();
            for (int j = 0; j < count - 1; j = j + 2) {
                int peek = Integer.parseInt(st.nextToken()) - 1;
                int distance = Integer.parseInt(st.nextToken());

                lists[index].add(new Node(peek, distance));
            }
        }

        // 아무 노드나 시작 노드로 설정해서 DFS
        DFS(0, 0);

        // 가장 컸던 index를 노드로 설정해서 DFS
        DFS(maxNodeLastIndex, 0);

        System.out.println(maxDistance);
    }

    public static void DFS(int index, int distance) {
        // 해당 index 확인 처리
        isChecked[index] = true;

        // 지금 노드가 마지막 노드인지 확인하는 변수 (더이상 확인할 노드가 없는지)
        boolean isEndNode = true;

        // 해당 index의 연결된 트리 정점을 모두 확인
        for (int i = 0; i < lists[index].size(); i++) {
            // 연결된 트리 정점 꺼내기
            Node node = lists[index].get(i);

            // 해당 node가 확인된 node인지 체크
            if (!isChecked[node.peak]) {
                // 다음 노드가 존재하므로 해당 변수를 false로 처리
                isEndNode = false;

                // 다음 노드까지 거리와 지금 maxDistance 거리 중에 큰 값을 maxDistance로 설정
                maxDistance = Math.max(maxDistance, distance + node.distance);

                // 해당 node DFS 실행
                DFS(node.peak, distance + node.distance);

            }
        }

        // 해당 index 확인 처리 취소
        isChecked[index] = false;

        // 해당 인덱스가 끝 인덱스이고 최대 거리와 지금 distance 거리가 동일할 경우,
        // 해당 index가 두 정점의 길이가 가장 길 때 그 중 하나의 정점이므로 변수로 저장
        if (isEndNode && maxDistance == distance) {
            maxNodeLastIndex = index;
        }
    }

    public static class Node {
        public int peak;
        public int distance;
        public Node(int peek, int distance) {
            this.peak = peek;
            this.distance = distance;
        }
    }
}