문제
전산학(Computer science)에서 트리란 사이클이 없는 그래프를 말한다. 트리(Tree)라는 이름이 의미하듯, 이러한 구조는 나무의 모습에서 유래한다. 즉, 트리의 각 간선(edge)들이 나무의 가지를 나타내고, 각 정점(node)들은 가지가 갈라지는 지점을 의미한다. 또한 트리의 루트는 나무의 뿌리를 의미한다. 이러한 구조는 일반적인 나무의 구조에 해당하지만, 트리 자체의 성질에 주목하면 실제 나무와는 다소 다른 구조가 되기도 한다.
우리가 생각하려는 나무는 루트가 없는 트리이다. 이때 트리의 각각의 간선은 나무의 가지에 해당하고, 트리의 각 정점은 나무 위에서 열매가 매달려있는 지점을 의미한다. 각각의 정점에는 몇 개의 열매가 매달려 있다. 물론 열매 없이 가지가 갈라지는 경우도 있으므로, 이러한 경우는 그 노드에 0개의 열매가 매달려 있다고 생각하기로 하자.
이러한 나무 위에 한 마리의 벌레가 있다. 이 벌레는 임의의 정점에서 이동하기 시작한다. 벌레가 한 정점에 있을 때에는, 그 정점에 있는 열매들을 먹을 수 있다. 열매들을 다 먹은 후에는 가지를 따라서 다른 정점으로 이동한다. 만약 이동할 수 있는 가지가 여러 개 있다면 그 중 하나를 임의로 선택하지만, 한 번 지났던 가지는 다시 지날 수 없다. 벌레의 이동은 더 이상 이동할 수 있는 정점이 없을 때에 끝난다.
나무의 모양이 주어졌을 때, 벌레가 최대로 먹을 수 있는 열매의 수와 이때 어느 정점에서 이동을 시작해야 하는지를 알아내는 프로그램을 작성하시오.
입력
첫째 줄에는 트리의 정점의 개수를 나타내는 정수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 차례로 1번, 2번, …, n번 정점에 매달려 있는 열매의 개수가 주어진다. 다음 n-1개의 줄에는 트리의 각 간선을 나타내는 서로 다른 두 자연수 A, B(1 ≤ A, B ≤ n)가 주어진다. 이는 트리의 A번 정점과 B번 정점이 연결되어 있음을 의미한다. 나무에 매달려 있는 열매의 총 개수는 231-1 (2,147,483,647)개를 넘지 않는다.
출력
첫째 줄에 벌레가 먹을 수 있는 열매의 최대 개수와, 이때 이동을 시작할 정점의 번호를 출력한다. 답이 여러 개 있을 경우에는 정점의 번호가 가장 작은 경우를 출력한다.
접근 방법
-
'트리의 지름' https://www.acmicpc.net/problem/1167 이라는 문제가 있습니다. 간단하게 요약하면 트리의 한 노드로부터 다른 노드까지의 거리가 가장 먼 두 노드를 찾는 문제입니다.
-
나무 위의 벌레는 해당 문제의 변형입니다. 다만 우리는 지름이 아닌 벌레가 먹는 최대 과일 수를 찾을 뿐입니다.
-
트리의 지름과 같이 아무 노드 (노드 개수가 1개부터 시작이므로, 여기서는 1번 노드 기준입니다)를 기준으로 BFS 혹은 DFS로 트리를 탐색하며 최대로 먹을 때의 마지막 노드를 찾습니다. 마지막 노드를 찾았다면 해당 노드를 시작으로 다시 한번 BFS, DFS 탐색을 진행해 우리가 원하는 최대로 먹을 수 있는 두 노드를 찾을 수 있습니다.
-
결과 출력은 작은 시작점 노드를 반환해야 하므로 비교 후 출력합니다.
⚠️주의할 점⚠️
- 모든 가지에 0 개의 과일이 달린 경우가 존재 할 수 있습니다.
- 우리가 찾은 결과 노드에 달린 과일이 0개인 경우, 이전 노드의 index가 더 작을 수 있습니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
public class BugOnTree {
static int n;
static int[] fruits;
static ArrayList<Integer>[] tree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
String[] fruit = br.readLine().split(" ");
tree = new ArrayList[n + 1];
fruits = new int[n + 1];
// fruits init
for (int i = 1; i < n + 1; i++) {
fruits[i] = Integer.parseInt(fruit[i - 1]);
}
for (int i = 0; i < n + 1; i++) {
tree[i] = new ArrayList<>();
}
// vertex init
for (int i = 0; i < n - 1; i++) {
String[] vertex = br.readLine().split(" ");
int x = Integer.parseInt(vertex[0]);
int y = Integer.parseInt(vertex[1]);
tree[x].add(y);
tree[y].add(x);
}
// start from 1
StringBuilder sb = new StringBuilder();
int[] maxNode = maximumFruits(1);
int[] result = maximumFruits(maxNode[1]);
sb.append(result[0]).append(' ').append(Math.min(maxNode[1], result[1]));
System.out.println(sb);
}
public static int[] maximumFruits(int start) {
int maxFruits = fruits[start]; // bug can eat maximum cnt
int maxNode = start;
int[] visit = new int[n + 1];
Arrays.fill(visit, -1); // 모두 0 일수 있으므로
ArrayDeque<Integer> dq = new ArrayDeque<>();
visit[start] = maxFruits;
dq.offerLast(start);
while (!dq.isEmpty()) {
int now = dq.removeFirst();
for (int next : tree[now]) {
if (visit[next] == -1) {
visit[next] = visit[now] + fruits[next];
dq.offerLast(next);
if (maxFruits < visit[next]) {
maxFruits = visit[next];
maxNode = next;
} else if (maxFruits == visit[next] && next < maxNode) {
maxFruits = visit[next];
maxNode = next;
}
}
}
}
return new int[]{maxFruits, maxNode};
}
}결과
