boj-1967 트리의 지름

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

문제 소개

트리에서는 어떤 두 노드를 선택해도 경로가 단 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쭉 잡아당길 때 가장 길게 늘어나는 경우가 있는데, 이럴 때 트리의 모든 노드들이 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. (트리에 존재하는 모든 경로들 중 가장 긴 것의 길이이기도 하다)

노드의 개수 n (1 <= n <= 10000)과 n - 1개의 간선에 대한 정보가 주어졌을 때, 트리의 지름을 구하자.

간선의 정보는 세 정수로 이루어지며 첫 번째 정수는 부모 노드, 두 번째 정수는 자식 노드, 세 번째 노드는 간선의 가중치를 나타낸다.

문제 풀이

DFS를 이용하여 풀이하였다.

트리의 지름을 만들 수 있는 두 노드의 최소한의 조건은 말단 노드(또는 잎 노드)이기 때문에, 한 말단 노드에서 다른 말단 노드로 가는 경로의 길이 중 최대값을 구하는 방식으로 풀이하였다.

DFS를 사용하려면 먼저 트리가 연결된 형태를 인접 행렬 또는 인접 리스트로 나타내야 한다. 최초에는 무식하게 인접 행렬로 구현했는데, 생각해 보면 노드의 개수가 최대 10000개이고 int형의 사이즈가 4 bytes이니 단순 계산을 해도 10000 * 10000 * 4 bytes = 400 MB로 문제의 메모리 제한인 128 MB를 훌쩍 뛰어넘는 수치였다.

당연하게도 메모리 초과를 만났고, 인접 리스트로 다시 풀이를 시도하였다. 인접 리스트가 메모리 차원에서 효율적인 이유는 당연했다. 인접 행렬로 구현한 경우 n * n개의 공간을 할당하지만 간선의 개수는 n - 1 개이기 때문에 n이 커질수록 데이터가 매우 sparse한 모습을 보여주기 때문이다.

adj는 vector<vector<pair<int, int>>>와 같은 자료형을 갖으며, adj[1]는 노드1과 연결된 다른 노드들의 정보를 갖고 있다. pair의 first는 연결된 노드의 번호, second는 가중치를 의미한다.

n - 1개의 간선을 입력받은 후 각 노드의 말단 노드 여부를 leaf에 저장한다. 단순히 adj[i].size()가 1이라면 연결된 간선이 하나, 즉 말단 노드임을 의미한다.

다음으로는 1번 노드부터 n번 노드까지 말단 노드인 경우에 함수 dfs()를 통해 다른 말단 노드까지의 경로를 탐색하며 가중치를 acc에 가중하며 결과값 중 최대값을 찾게 한다.

dfs()내에 말단 노드에의 도착 여부는 if (leaf[current] && acc)로 하였는데, 말단 노드에 도착한 경우 중 시작점을 제외하기 위해서다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<std::vector<std::pair<int, int>>> adj_list_t;
typedef std::vector<bool> check_t;

int n;
int acc = 0;
int result = 0;

void dfs(int current, adj_list_t& adj, check_t& visited, check_t& leaf) {
	visited[current] = true;

    // 시작점을 제외한 말단 노드에 도착한 경우
	if (leaf[current] && acc) {
        // result보다 큰 acc값인 경우
		if (acc > result) {
			result = acc;
		}
		return;
	}

    // acc의 값을 변화시키며 탐색 진행
	for (std::pair<int, int>& t : adj[current]) {
		if (!visited[t.first]) {
			acc += t.second;
			dfs(t.first, adj, visited, leaf);
			acc -= t.second;
		}
	}
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	adj_list_t adj(n + 1, vector<pair<int, int>>());    // 인접 리스트
	check_t visited(n + 1, false);                      // 방문 처리
	check_t leaf(n + 1, false);                         // 말단 노드 여부

	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	for (int i = 1; i <= n; i++) {
		if (adj[i].size() == 1) {
			leaf[i] = true;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (leaf[i]) {
			acc = 0;
			dfs(i, adj, visited, leaf);
			fill(visited.begin(), visited.end(), false);
		}
	}
	cout << result << '\n';

	return 0;
}