JUINTINATION
백준 1167번: 트리의 지름 본문
문제
https://www.acmicpc.net/problem/1167
풀이
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이인 트리의 지름을 구하는 문제입니다. 1967번 문제와 유사합니다. 1967번 문제와 다른 점은 입력에서 -1을 입력할 때 까지 해당 노드에 연결된 노드의 정보를 입력한다는 것입니다.
접근
1967번 문제와 연결됩니다. 트리의 간선들에 가중치가 있기 때문에 단순히 가장 왼쪽에 있는 노드와 가장 오른쪽에 있는 노드 사이의 거리를 구하는 문제가 아닙니다. 처음에 이 문제를 보고 루트 노드에서 가장 먼 노드와 두 번째로 먼 노드 사이의 거리를 구해볼까 했는데 이는 두 노드가 같은 경로에 있을 가능성이 있습니다. 그래서 루트 노드에서 가장 먼 노드를 찾고 그 노드에서부터 가장 먼 노드 사이의 거리를 구하는 방식으로 문제를 해결했습니다. 각 노드에서 가장 먼 노드를 찾기 위해 dfs 알고리즘을 사용하였습니다.
코드
자바
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class node {
int data, cost;
public node(int data, int cost) {
this.data = data;
this.cost = cost;
}
}
public class Main {
static int tmp, max = 0;
static boolean[] visited;
static ArrayList<node>[] list;
public static void dfs(int idx, int len) { // (2)
if (len > max) {
max = len;
tmp = idx;
}
visited[idx] = true;
for (node n : list[idx]) { // (1)
if (!visited[n.data]) {
dfs(n.data, len + n.cost);
}
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int v = Integer.parseInt(br.readLine());
list = new ArrayList[v + 1];
visited = new boolean[v + 1];
for (int i = 1; i <= v; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < v; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
while (true) {
int data = Integer.parseInt(st.nextToken());
if (data == -1) break;
int cost = Integer.parseInt(st.nextToken());
list[n].add(new node(data, cost));
}
}
dfs(1, 0);
Arrays.fill(visited, false);
dfs(tmp, 0); // (3)
System.out.println(max);
}
}
1967번 문제와 연결됩니다. ArrayList[] 배열 list는 임의의 수 x번 노드에 연결된 다른 노드들의 번호와 해당 노드와의 거리를 저장해야 합니다. 그래서 트리의 노드 클래스 node는 list[x]와 연결된 노드의 번호 data와 해당 노드와의 거리 cost를 포함합니다.
모든 입력이 끝난 후 dfs(1, 0)을 실행하여 루트 노드인 1번 노드와 가장 먼 노드를 찾습니다. dfs(int idx, int len)에서 idx는 현재 탐색중인 노드의 번호를, len은 dfs 메소드를 실행했을 때 시작했던 노드와의 거리를 의미합니다.
(1) idx번 노드의 방문 여부를 true로 초기화한 뒤에 idx번 노드와 연결된 다른 노드를 확인합니다.
1967번 문제와 다르게 트리의 정점 개수가 2개 이상이기 때문에 list[idx]가 null이 아닌지 확인할 필요가 없습니다.(list[idx]가 null일 가능성이 없습니다. 즉, 탐색중인 노드는 반드시 다른 노드와 연결돼있습니다.) foreach문을 통해 list[idx]를 탐색합니다. 탐색중인 노드 e를 방문하지 않았다면(!visited[e.data]) dfs(e.data, len + e.cost)를 실행하여 다음 노드를 탐색합니다.
(2) 현재 탐색중인 노드까지의 길이가 max보다 큰지 확인합니다.
len > max라면 max를 len으로 초기화하고 루트 노드인 1번 노드와 가장 먼 노드의 번호를 의미하는 tmp를 idx로 초기화합니다.
(3) 위의 과정이 끝났다면 visited 배열을 모두 false로 초기화한 후 dfs(tmp, 0)을 실행합니다.
(1)번 과정과 (2)번 과정을 반복하면서 tmp번 노드와 가장 먼 노드를 탐색합니다.
모든 과정을 종료한 후에 max를 출력합니다.
C언어
#include <stdio.h>
#include <stdlib.h>
int v, tmp, max = 0, *visited;
typedef struct node {
int data, cost;
struct node* next;
} node;
void add(node* target, int data, int cost) {
node* now = (node*)malloc(sizeof(node));
now->data = data;
now->cost = cost;
now->next = target->next;
target->next = now;
return;
}
node* list[100001];
void dfs(int idx, int len) {
if (len > max) {
max = len;
tmp = idx;
}
visited[idx] = 1;
node* n = list[idx]->next;
while (n != NULL) {
if (!visited[n->data]) {
dfs(n->data, len + n->cost);
}
n = n->next;
}
}
main() {
scanf("%d", &v);
visited = (int*)malloc(sizeof(int) * (v + 1));
for (int i = 1; i <= v; i++) {
list[i] = (node*)malloc(sizeof(node));
list[i]->next = NULL;
visited[i] = 0;
}
for (int i = 0; i < v; i++) {
int n, data, cost;
scanf("%d", &n);
while (1) {
scanf("%d", &data);
if (data == -1) break;
scanf("%d", &cost);
add(list[n], data, cost);
}
}
dfs(1, 0);
for (int i = 1; i <= v; i++) {
visited[i] = 0;
}
dfs(tmp, 0);
printf("%d", max);
}
자바를 이용한 풀이와 동일합니다. ArrayList 배열은 연결리스트를 이용하여 구현했습니다.
결론
1967번 문제를 풀고 정리하면서 (1)번 과정에서 list[idx]가 null인 경우가 존재하지 않을 것 같다는 생각이 들었었는데 정점의 개수가 1일 경우에 1번 노드에 연결된 다른 노드가 존재하지 않기 때문에 런타임 에러 (NullPointer)가 발생했습니다. 하지만 이 문제는 정점의 개수가 1일 경우가 존재하지 않기 때문에 try-catch문 등을 사용할 필요없이 잘 해결할 수 있었습니다.
'백준 알고리즘 > 트리' 카테고리의 다른 글
백준 1967번: 트리의 지름 (0) | 2023.02.08 |
---|---|
백준 5639번: 이진 검색 트리 (0) | 2023.01.29 |
백준 2250번: 트리의 높이와 너비 (0) | 2023.01.24 |