오늘 풀어볼 문제는 트리 지름 구하기 문제이다.
✅ 1. 문제 설명
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력값은 다음과 같다.
- 노드 개수
- 노드 번호 / 연결된 노드 번호 / 가중치 / . . . / -1 (종료표시)
해당 트리의 답은 1번과 5번 노드의 총 가중치인 11이다.
✅ 2. 틀린 풀이
일단 난 접근을 다음과 같이 시도했다.
각 연결된 노드를 클래스로 만들고, 해당 출발->도착 노드로부터 갈 수 있는 최대치를 클래스에 저장하여 시간 단축을 하고자 했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Node {
int arrival;
long distance;
boolean isMax;
public Node(int arrival, long distance) {
this.arrival = arrival;
this.distance = distance;
}
public void setMax(){
this.isMax=true;
}
}
static List<Node>[] tree;
static boolean visited[];
static long answer=0L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int V = Integer.parseInt(br.readLine());
tree = new List[V+1];
visited = new boolean[V+1];
for(int i=1; i<=V; i++){
tree[i]=new ArrayList<>();
}
for(int i=1; i<=V; i++){
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
String s = st.nextToken();
while(!s.equals("-1")){
int arrival=Integer.parseInt(s);
long distance=Integer.parseInt(st.nextToken());
tree[from].add(new Node(arrival, distance));
s = st.nextToken();
}
}
for(int i=1; i<=V; i++){
answer = Math.max(answer, dfs(i));
}
System.out.println(answer);
}
static long dfs (int start) {
long distance=0L;
visited[start]=true;
for(int i=0; i<tree[start].size(); i++) {
Node next = tree[start].get(i);
if(visited[next.arrival]) continue;
if(next.isMax) {
distance=next.distance;
}
else {
next.distance=dfs(next.arrival)+next.distance;
distance=Math.max(next.distance, distance);
next.setMax();
}
}
visited[start]=false;
return distance;
}
}
위와 같이 A->B로의 최대치가 계산된 경우, 클래스 내 isMax를 true로 변경하고, 그 다음 접근시에는 dfs 함수를 타고 가는 것이 아닌 바로 최대치를 반환하고 끝내는 로직이었다.
ㅋㅋ 근데 ㅋㅋ 6%에서 ㅋㅋ 틀렸다 ㅋㅋ 이유는 도저히 못 찾겠다. 찾으면 인정해드림
그래서 결국 답지를 봤다...
✅ 3. 옳은 풀이
해당 문제는 트리의 특징을 알면 된다.
트리의 특징
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
4. 트리에는 사이클이 존재할 수 없다.
트리 지름 구하는 최적의 해
- 임의의 노드(1번 노드)에서 시작하여 가장 거리가 먼 노드(트리의 한쪽 끝점)를 찾음.
- 찾은 끝점에서 다시 DFS를 수행하여 가장 먼 거리를 계산.
- 이 거리가 트리의 지름임!!!
코드는 간단하게 나온다.
✅4. 핵심 코드
4-1. Node Class
static class Node {
int arrival;
long distance;
public Node(int arrival, long distance) {
this.arrival = arrival;
this.distance = distance;
}
}4-2. 전역 변수 및 입력 함수
static List<Node>[] tree;
static boolean[] visited;
static int MaxPoint;
static long MaxDistance;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int V = Integer.parseInt(br.readLine());
tree = new ArrayList[V + 1];
visited = new boolean[V + 1];
for (int i = 1; i <= V; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 1; i <= V; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
while (st.hasMoreTokens()) {
int to = Integer.parseInt(st.nextToken());
if (to == -1) break;
long distance = Long.parseLong(st.nextToken());
tree[from].add(new Node(to, distance));
}
}
....
4-3. dfs 함수 호출
....
// 첫 번째 DFS: 임의의 노드에서 가장 먼 노드 찾기
dfs(1, 0); //임의의 한 노드에서 시작
// 두 번째 DFS: 가장 먼 노드에서 시작하여 트리의 지름 계산
Arrays.fill(visited, false); // 방문 배열 초기화
MaxDistance=0;
dfs(MaxPoint, 0);
System.out.println(MaxDistance);
}
static void dfs(int start, long distance) {
visited[start] = true;
if(distance>MaxDistance){
MaxDistance=distance;
MaxPoint=start;
}
for(Node next : tree[start]) {
if(!visited[next.arrival]) {
dfs(next.arrival, distance+ next.distance);
}
}
}4-4. 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int arrival;
long distance;
public Node(int arrival, long distance) {
this.arrival = arrival;
this.distance = distance;
}
}
static List<Node>[] tree;
static boolean[] visited;
static int MaxPoint;
static long MaxDistance;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int V = Integer.parseInt(br.readLine());
tree = new ArrayList[V + 1];
visited = new boolean[V + 1];
for (int i = 1; i <= V; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 1; i <= V; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
while (st.hasMoreTokens()) {
int to = Integer.parseInt(st.nextToken());
if (to == -1) break;
long distance = Long.parseLong(st.nextToken());
tree[from].add(new Node(to, distance));
}
}
// 첫 번째 DFS: 임의의 노드에서 가장 먼 노드 찾기
dfs(1, 0); //임의의 한 노드에서 시작
// 두 번째 DFS: 가장 먼 노드에서 시작하여 트리의 지름 계산
Arrays.fill(visited, false); // 방문 배열 초기화
MaxDistance=0;
dfs(MaxPoint, 0);
System.out.println(MaxDistance);
}
static void dfs(int start, long distance) {
visited[start] = true;
if(distance>MaxDistance){
MaxDistance=distance;
MaxPoint=start;
}
for(Node next : tree[start]) {
if(!visited[next.arrival]) {
dfs(next.arrival, distance+ next.distance);
}
}
}
}
열심히 했음. 끝
