[Baekjoon] 1167_트리의 지름

Gold II

문제(출처: https://www.acmicpc.net/problem/1167)

---

< 트리의 지름 >

 

문제 풀이 

 

처음에는 정점 1에서 dfs 탐색을 통해 지름을 구했다. 내가 구현한 코드 방식으로는 만약 정점 1에서 3개의 자식이 있다면 각 DFS를 통해 3개의 거리를 더한 값이 트리의 지름이 되는 것이었다. 하지만 트리의 지름은 임의의 두 점 사이의 거리 중에서 가장 긴 것을 뜻하므로 제대로 된 답을 구할 수 없었다.

 

트리의 지름을 구하는 방법을 찾아보니 다음과 같았다.

1. DFS를 통해 임의의 정점(a)으로부터 가장 먼 정점(b)을 구함
2. 가장 먼 정점(b)으로부터 DFS를 통해 가장 먼 정점(c)을 구함
3. 2번에서 구한 가장 먼 정점(b)과 새로 구한 가장 먼 정점(c)의 거리가 트리의 지름이 된다. 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class _1167_ { // 트리의 지름
	static int max, max_num;
	static boolean visited[];
	static ArrayList<ArrayList<Node>> list;

	static class Node {
		private int num;
		private int d;

		public Node(int num, int d) {
			this.num = num;
			this.d = d;
		}
	}

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

		int v = Integer.parseInt(bf.readLine());

		list = new ArrayList<>();
		visited = new boolean[v + 1];

		for (int i = 0; i <= v; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < v; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			while (st.hasMoreTokens()) {
				int b = Integer.parseInt(st.nextToken());
				if (b == -1)
					break;
				int d = Integer.parseInt(st.nextToken());
				list.get(a).add(new Node(b, d));
			}
		}

		int result = 0, result_num = 0;
		visited[1] = true;

		// 임의의 정점부터 가장 먼 정점 구하기
		for (int i = 0; i < list.get(1).size(); i++) {
			if (!visited[list.get(1).get(i).num]) {
				max = list.get(1).get(i).d;
				max_num = list.get(1).get(i).num;

				dfs(list.get(1).get(i).num, list.get(1).get(i).d);
				if (result < max) {
					result = max;
					result_num = max_num;
				}
			}
		}

		// 구해진 정점에서 가장 먼 정점 구하기
		max = 0;
		for (int i = 0; i <= v; i++) {
			visited[i]=false;
		}

		dfs(result_num, 0);

		System.out.println(max);
	}

	private static void dfs(int num, int d) {
		visited[num] = true;

		for (int i = 0; i < list.get(num).size(); i++) {
			if (!visited[list.get(num).get(i).num]) {
				if (max < d + list.get(num).get(i).d) {
					max = d + list.get(num).get(i).d;
					max_num = list.get(num).get(i).num;
				}
				dfs(list.get(num).get(i).num, d + list.get(num).get(i).d);
			}
		}
	}
}

변수)
v : 정점의 개수
list : 각 정점의 간선의 정보 저장
visited : 방문 여부
a, b, d : 정점 번호, 연결된 정점 번호, 그 정점까지의 거리
max, max_num : 임의의 정점부터 가장 먼 정점의 거리와 정점
result, result_num : 임의의 정점부터 가장 먼 정점의 거리와 정점의 최댓값

 

Node

정점의 번호와 거리

 

Main

정점의 개수와 간선의 정보를 입력받아 저장한다. 1번 정점을 시작점으로 임의로 두고 DFS를 통해 1번 정점으로부터 가장 먼 거리에 있는 정점을 구한다. 가장 먼 거리에 있는 정점을 시작점으로 두고 DFS를 통해 트리의 지름을 구한다.

 

dfs (정점, 거리)

먼저, 정점을 방문 표시로 바꾼다. 현재 정점과 연결된 정점을 탐색하며 아직 방문하지 않았다면 거리를 최댓값으로 업데이트한 후 DFS 함수 호출한다.

---

---