JUINTINATION

백준 1167번: 트리의 지름 본문

백준 알고리즘/트리

백준 1167번: 트리의 지름

DEOKJAE KWON 2023. 2. 8. 15:12
반응형

문제

https://www.acmicpc.net/problem/1167

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net


풀이

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이인 트리의 지름을 구하는 문제입니다. 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문 등을 사용할 필요없이 잘 해결할 수 있었습니다.

728x90

'백준 알고리즘 > 트리' 카테고리의 다른 글

백준 1967번: 트리의 지름  (0) 2023.02.08
백준 5639번: 이진 검색 트리  (0) 2023.01.29
백준 2250번: 트리의 높이와 너비  (0) 2023.01.24
Comments