[Java] 백준 BOJ / 1167번: 트리의 지름

트리의 지름

문제

---

문제 설명

트리의 정점의 개수와 간선에 대한 정보들이 주어질때 이 트리의 한 정점에서 어떤 정점까지의 거리를 구했을 때 그 중 가장 긴 거리를 트리의 지름이라고 한다.

트리의 지름을 출력하면 되는 문제이다.

---

구현

트리의 지름을 구하려면 가장 먼 두 정점을 알아야 한다.

그래서 생각을 해봤는데 일단 어느 한 정점에서 DFS 를 시작하면 지름의 한 끝점으로 이동할 거고, 거기서 다시 DFS를 하면 지름의 길이가 계산 된다. 라는 가정을 세웠다.

그래서 아무 정점에서 시작하는 DFS, 그리고 거기서 나온 정점에서 시작하는 DFS 이렇게 총 2번의 DFS 를 거치기로 생각했다.

DFS 함수에는 시작한 노드와 현재까지의 거리를 넘겨준다.

public static void dfs(int node, int dist) {
	//구현
}

이 함수 내에서 방문처리를 해주고, 현재 노드까지의 거리인 dist 가 maxDist 보다 크다면 새로 초기화를 시켜주고 현재 노드를 가장 먼 노드를 저장하는 변수인 farthestNode에 저장해준다.

그 후에 현재 노드의 인접 노드들을 탐색하며 방문하지 않았다면 다시 DFS를 도는 방식으로 해주었다.

public static void dfs(int node, int dist) {
    visited[node] = true;

    if (dist > maxDist) {
		maxDist = dist;
		farthestNode = node;
    }
    for (int[] next : graph[node]) {
      	int nextNode = next[0];
      	int weight = next[1];
        if (!visited[nextNode]) {
          	dfs(nextNode, dist + weight);
		}
	}
}

---

코드

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

public class Main_1167 {
  static int v;
  static ArrayList<int[]>[] graph;
  static boolean[] visited;
  static int maxDist;
  static int farthestNode;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    v = Integer.parseInt(br.readLine());
    graph = new ArrayList[v + 1];
    for (int i = 1; i <= v; i++) {
      graph[i] = new ArrayList<>();
    }

    for (int i = 1; i <= v; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int node = Integer.parseInt(st.nextToken());
      int dest;
      int weight;
      while ((dest = Integer.parseInt(st.nextToken())) != -1) {
        weight = Integer.parseInt(st.nextToken());
        graph[node].add(new int[]{dest, weight});
      }
    }
    visited = new boolean[v + 1];
    dfs(1,0);

    visited = new boolean[v + 1];
    maxDist = 0;
    dfs(farthestNode,0);

    System.out.println(maxDist);
  }

  public static void dfs(int node, int dist) {
    visited[node] = true;

    if (dist > maxDist) {
      maxDist = dist;
      farthestNode = node;
    }
    for (int[] next : graph[node]) {
      int nextNode = next[0];
      int weight = next[1];
      if (!visited[nextNode]) {
        dfs(nextNode, dist + weight);
      }
    }
  }
}