백준 1167, 트리의 지름

문제

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

풀이

예전에 비슷한 이야기를 들은 적이 있는 것 같아서 아무 점에서나 가장 먼 곳을 찾고 중복된 것 0으로 만들고 두번째로 먼 것을 찾으면 가장 길이가 긴 것이 나온다라는 것으로 구현했는데 안되길래

질문 게시판 뒤져보니까 그냥 가장 먼 곳 찾고 거기서 다시 먼 곳 찾으면 된다고 한다. 하니까 쉽게 되었다.

다음엔 풀이를 대충 생각하지 말자

나중에 증명을 해보는 것도 좋을 것 같다.

실수

• 풀이가 이상했고 코드라도 제대로 짯으면 됐을텐데 새벽이라 대충 짯다

코드

스파게티이다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<vector<pair<int, int>>> origin_graph(100001, vector <pair<int, int>>(0, make_pair(0, 0)));
vector<vector<pair<int, int>>> graph(100001, vector <pair<int, int>>(0, make_pair(0, 0)));
vector<int> visit(100001, 0);

int max_v;
int dis = 0;

int dfs_max(int now) {

	int res = 0;
	int temp_v;
	int temp;

	visit[now] = 1;

	for (int i = 0; i < graph[now].size(); i++) {

		if (visit[graph[now][i].first] == 0) {

			temp_v = max_v;
			
			temp = dfs_max(graph[now][i].first) + graph[now][i].second;

 			if (res < temp) {

				if (graph[now][i].second == 0)
					dis += origin_graph[now][i].second;

				
				res = temp;

			}

			else {

				dis = 0;
				max_v = temp_v;

			}

		}

	}

	if (res == 0)
		max_v = now;

	return res;

}

int main() {

	int v;

	int temp1, temp2, temp3, temp4;

	int first = 0;

	scanf("%d", &v);

	for (int i = 1; i <= v; i++) {

		scanf("%d", &temp1);

		while (1) {

			scanf("%d", &temp2);

			if (temp2 == -1)
				break;

			scanf("%d", &temp3);
			
			graph[temp1].push_back(make_pair(temp2, temp3));

			origin_graph[temp1].push_back(make_pair(temp2, temp3));


		}

	}

	temp1 = dfs_max(1);

	for (int i = 1; i <= v; i++)
		visit[i] = 0;

	temp2 = dfs_max(max_v); // 다시 찾음

	printf("%d", temp2);

	return 0;

}