백준 1167 : 트리의 지름

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

1.접근

• 트리의 하나의 노드로부터 다른 노드까지 탐색을 통해 접근하고, 공통의 max거리를 업데이트 하면서 진행한다.
• 최단, 최장 길이에 대한 것이므로 BFS로 먼저 접근했다. (큰 차이가 없는 것 같아 DFS로도 구현했음)
• 시작 정점이 어딘지에 따라 결과가 다르게 나오는 문제점이 생긴다.
  => 시작 정점으로부터 가장 먼 정점에서 다시 한번 탐색을 진행해주어야 함
  (모든 정점으로부터 시작해볼 수 있지만, 시간 초과 발생)

2. 반례

• 문제의 예시에서는 시작 정점에서 트리의 지름이 나오지 않는 경우가 없었음
• 질문 게시판에서 혜자 반례들을 찾음...
  https://www.acmicpc.net/board/view/67245

case 1)

6
1 2 3 -1
2 1 3 5 3 3 5 -1
3 2 5 4 7 -1
4 3 7 -1
5 2 3 6 5 -1
6 5 5 -1
답 : 20

case 2)

4
1 2 7 3 2 -1
2 1 7 -1
3 1 2 4 3 -1
4 3 3 -1
답 : 12

case 3)

5
1 2 7 3 2 5 10 -1
2 1 7 -1
3 1 2 4 3 -1
4 3 3 -1
5 1 10 -1
답 : 17

case 4)

4
1 2 5 3 9 -1
2 1 5 -1
3 1 9 4 8 -1
4 3 8 -1
답 : 22

3. 나의 풀이

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;

vector<pair<int,int>> tree[MAX];
int v;
queue<pair<int,int>> q;
int maxcost = 0;
bool visited[MAX];
int longestNode = 0; //시작 노드로부터 가장 멀리 있는, 최대노드


void dfs(int node,int cost) {
	visited[node] = true;

	if (cost > maxcost) {
		maxcost = cost; //최댓값 업데이트
		longestNode = node; //최대노드 변경
	}

	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node].at(i).first;
		int nextcost = tree[node].at(i).second;

		if (!visited[next]) {
			dfs(next,cost+nextcost);
		}
	}
}


void bfs(int node,int cost) {

	q.push(make_pair(node,cost));

	while (!q.empty()) {
		node = q.front().first;
		cost = q.front().second;
		//cout << "node : " << node << ", cost : " << cost << "\n";
		visited[node] = true;
		q.pop();

		for (int i = 0; i <tree[node].size(); i++) {
			int next = tree[node].at(i).first;
			int nextcost = tree[node].at(i).second;

			if (!visited[next]) { //다음 노드를 방문하지 않았다면
				q.push(make_pair(next, cost+nextcost));
				if (cost + nextcost > maxcost) { 
					maxcost = cost+ nextcost; //최댓값 업데이트
					longestNode = next; //최대노드 변경
					//cout << next << "에서 최대거리 : " << maxcost << "\n";
				}
			}
		}
	}
}
int main() {
	cin >> v;

	for (int i = 0; i < v; i++) {
		int x, y, cost;
		cin >> x;

		cin >> y;
		while (y != -1) {
			cin >> cost;
			tree[x].push_back(make_pair(y,cost));
			tree[x].push_back(make_pair(x, cost));
			cin >> y;
		}
	}


	bfs(1,0);
	memset(visited, false, sizeof(visited));
	bfs(longestNode, 0); //시작 노드로부터 가장 먼 노드에서 다시 BFS해봄

	cout << maxcost << "\n";

}