백준 1967 트리의 지름 - JAVA (자바)
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net
문제
트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.
이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.
트리의 노드는 1부터 n까지 번호가 매겨져 있다.
예제 입력 :
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10
예제 출력 :
45
풀이 1번 :
모든 노드를 시작점으로 DFS(깊이 우선 탐색)을 진행해서 트리의 지름을 구하는 코드이다.
모든 노드에 대해서 탐색하기 때문에 비효율적인 코드이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static class Node {
int dest;
int weight;
Node(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
private static int N;
private static ArrayList<Node>[] adjList;
private static boolean[] visited;
private static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList[start].add(new Node(end, weight));
adjList[end].add(new Node(start, weight));
}
visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
Arrays.fill(visited, false);
dfs(i, 0);
}
System.out.println(max);
}
private static void dfs(int start, int sum) {
visited[start] = true;
max = Math.max(max, sum);
for (Node next : adjList[start]) {
if (!visited[next.dest]) {
visited[next.dest] = true;
dfs(next.dest, sum + next.weight);
}
}
}
}
풀이 2번 - 실행시간
풀이 2번 :
트리는 사이클이 없는 연결 그래프를 말한다. 그렇기 때문에 리프노드 즉 자식이 없는 노드에서
DFS(깊이 우선 탐색)을 진행하면 트리의 지름을 구할 수 있다.
그래서 리프노드를 우선적으로 찾고 모든 리프노드에서 DFS를 진행하여 트리의 지름을 찾는 코드이다.
이 방법은 리프노드에서만 탐색을 진행하기 때문에 1번 풀이보다 효율적이긴 하지만
여전히 모든 리프노드에서 탐색을 진행하기 때문에 여전히 비효율적인 코드이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static class Node {
int dest;
int weight;
Node(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
private static int N;
private static ArrayList<Node>[] adjList;
private static boolean[] visited;
private static boolean[] leaf;
private static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
leaf = new boolean[N + 1];
Arrays.fill(leaf, true);
adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList[start].add(new Node(end, weight));
adjList[end].add(new Node(start, weight));
leaf[start] = false;
}
visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
if (!leaf[i]) {
continue;
}
Arrays.fill(visited, false);
dfs(i, 0);
}
System.out.println(max);
}
private static void dfs(int start, int sum) {
visited[start] = true;
max = Math.max(max, sum);
for (Node next : adjList[start]) {
if (!visited[next.dest]) {
visited[next.dest] = true;
dfs(next.dest, sum + next.weight);
}
}
}
}
풀이 2번 - 실행시간
풀이 3번 :
임의의 노드에서 DFS를 진행해서 가장 먼 노드를 찾고
가장 먼 노드에서 DFS를 진행하여 트리의 지름을 구하는 방식이다.
트리의 지름은 리프노드와 리프노드 사이에 존재한다.
임의의 노드에서 DFS를 진행하면 트리의 지름의 한쪽 끝에 있는 노드를 구할 수 있다.
그리고 첫 번째 DFS로 찾은 노드에서 다시 DFS를 수행하면, 이 노드에서 가장 먼 또 다른 노드를 찾을 수 있다.
그러면 첫 번째 DFS로 찾은 노드와 두 번째 DFS에서 찾은 노드 사이의 경로가 트리의 지름이 된다.
그렇게 되면 탐색을 두 번만 진행하기 때문에 효율적인 방법으로 트리의 지름을 구할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static class Node {
int dest;
int weight;
Node(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
private static int N;
private static ArrayList<Node>[] adjList;
private static boolean[] visited;
private static int max, distantNode;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
if (N == 1) {
System.out.println(0);
return;
}
adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList[start].add(new Node(end, weight));
adjList[end].add(new Node(start, weight));
}
visited = new boolean[N + 1];
// 임의의 노드 1번에서 DFS를 진행
dfs(1, 0);
Arrays.fill(visited, false);
max = 0;
// 가장 먼 노드에서 DFS를 진행
dfs(distantNode, 0);
System.out.println(max);
}
private static void dfs(int start, int sum) {
visited[start] = true;
if (max < sum) {
max = sum;
distantNode = start;
}
for (Node next : adjList[start]) {
if (!visited[next.dest]) {
dfs(next.dest, sum + next.weight);
}
}
}
}
풀이 3번 - 실행시간
3가지 풀이 실행시간 비교
'Baekjoon' 카테고리의 다른 글
| [BOJ / 백준] 백준 1197 최소 스패닝 트리 - (자바 / JAVA) (0) | 2024.10.12 |
|---|---|
| [BOJ / 백준] 백준 1238 파티 - (자바 / JAVA) (0) | 2024.08.20 |
| [BOJ / 백준] 백준 16928 뱀과 사다리 게임 - (자바 / JAVA) (0) | 2024.07.31 |
| [BOJ / 백준] 백준 12841 정보대 등산 - (자바 / JAVA) (1) | 2024.07.10 |
