백준 1167번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	256MB	골드 2

---

풀이

 이 문제는 정말 며칠동안 고심하고 해결한 문제이다. 이 문제는 뭔가 무엇도 참조하지 않고 내가 직접 풀어보고 싶다는 욕망이 들었고, 이를 실제로 행한 문제이다.

 

 처음에는 별 생각없이 정점의 개수도 체크하지 않고 플로이드 워셜을 돌린 후, 트리의 지름을 찾고자 했다. 하지만 정점의 개수가 10만개인데 당연히 불가능한 풀이였고, 바로 폐기한 방법이다.

 

 두번째는 내가 풀이한 방법이다. 임의의 정점을 골랐을 때, 트리의 지름을 구성할 때 내가 선택한 정점이 트리의 지름에 낄 수도 있고 아닐수도 있다. 정확히 말하면, 트리의 지름은 내가 현재 위치한 정점을 사용할 수도 있고, 내가 위치한 정점의 서브트리 안에서 트리의 지름이 만들어 질수도 있다. 이 문제의 트리는 이진 트리가 아니기 때문에 서브트리는 1개일수도 있고, 3개 이상일수도 있다. 트리의 지름을 구하기 위해서는 각 서브트리에서 현재 위치한 정점으로 오기 위한 제일 긴 경로의 길이를 알아낸 후, 최댓값과 그 다음 최댓값의 합을 구한다. 이는 현재 위치한 정점을 지나는 경우에 만들어지는 트리의 지름이다. 물론 이는 답일수도 있고 아닐수도 있다. 그렇기 때문에 각 서브트리로 파고든 후, 같은 과정을 반복한다. 이렇게 구한 트리의 지름들 중에서 제일 큰 값을 구하면 그것이 트리의 지름이 될 것이다.

 

 여기까지 접근한 후, 구현을 했으나 계속되는 MLE 행진이었다. 구현에 문제가 있는줄 알았고, 며칠동안 고치고 고심하며 메모리를 최대한 줄여보았다. 하지만 MLE는 해결되지 않았고, 결국 지인에게 도움을 구했다. 지인이자 PS스승과 같은 사람이다. 내 풀이 방법은 실제로 맞는 방법이었고, 어디서 MLE가 나는지를 같이 고민했다. 정답은 의외로 다른 곳에 있었다. 예제입력에서는 정점 1부터 5까지 정보를 차례대로 입력해주지만, 실제로는 정점 1 정보 -> 정점 3 정보 -> 정점 2 정보 ... 처럼 뒤죽박죽으로 들어올 수 있다. 순서대로 들어온다는 조건은 어디에도 없기 때문이다. 나는 순서대로 들어올거라 착각하고 입력을 처리했고, 이런 문제로 인해 트리를 만든 것이 아닌, 무향 순환 그래프가 만들어졌고, 무한 재귀로 인해 메모리가 터진 것이다. 이를 고치고 AC를 받았다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> graph;
int answer = -1;

void input() {
	int tmp, dest, dist, n;
	cin >> n;
	graph.resize(n + 1);

	while(n--) {
		cin >> tmp;
		while(true) {
			cin >> dest;
			if (dest == -1) break;
			cin >> dist;
			graph[tmp].push_back({dest, dist});
		}
	}
}

void update(pair<int, int>& p, int val) {
	auto& [m1, m2] = p;
	if (val >= m1) {
		m2 = m1;
		m1 = val;
	}
	else if (val > m2) {
		m2 = val;
	}
}

int max_length(int cur, int parent) {
	pair<int, int> length = {0,0};

	for(auto& [child, dist] : graph[cur]) {
		if (child == parent) {
			continue;
		}
		update(length, dist + max_length(child, cur));
	}
	answer = max(answer, length.first + length.second);
	return length.first;
}

void sol() {
	max_length(1, -1);
	cout << answer;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}