백준 1967번 트리의 지름 (C++)

재채점으로 틀렸습니다 당해버려서 다시 푼 문제이다.
다 풀고 다른 사람 풀이를 찾아봤는데 내가 생각한 너비우선탐색 풀이는 없어서 남겨본다.

정석 풀이보다 비효율인 풀이지만 난 실제 코테에서 이런 문제를 마주쳐도 지금처럼 푸면 풀지 정석 풀이처럼 생각하지는 못할 거 같다 ㅠㅠ

문제링크

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

설명

트리의 지름을 구하는 문제이다.
트리의 지름을 구성하는 양 끝 점은 자식 노드가 없는 노드(리프 노드)일 수 밖에 없다.

그러므로 리프 노드를 따로 구한 후, 모든 리프 노드를 시작점으로 bfs를 진행하여 가장 큰 값을 구한다.
조금이라도 효율성을 살리기 위해 이전에 체크한 리프 노드는 따로 방문 체크를 해주어 bfs를 중복으로 실행하는 것을 방지한다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define p pair<int, int>
#define N 10001

using namespace std;

struct node {
	int start, pos, dis;
};

int n, answer;
vector<int> arr;
vector<p> path[N];
bool check[N], visited[N];

void input()
{
	cin >> n;

	for (int i = 1; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		path[a].push_back({ b, c });
		path[b].push_back({ a, c });
		check[a] = 1;
	}
}

// 자식이 없는 노드 골라주기
void setarr()
{
	for (int i = 1; i <= n; i++)
		if (!check[i])
			arr.push_back(i);
}

// 중복 체크 방지를 위해 지금까지 찾아온 자식 노드 방문 체크
void setvisited(int k)
{
	for (int i = 0; i <= k; i++)
		visited[arr[i]] = 1;
}

void solution()
{
	setarr();

	for (int i = 0; i < arr.size(); i++)
	{
		memset(visited, 0, sizeof(visited));
		queue<node> q;
		q.push({ arr[i], arr[i], 0 });
		setvisited(i);

		while (!q.empty())
		{
			int start = q.front().start;
			int pos = q.front().pos;
			int dis = q.front().dis;
			q.pop();

			answer = max(answer, dis);

			for (int j = 0; j < path[pos].size(); j++)
			{
				int npos = path[pos][j].first;

				if (visited[npos])
					continue;

				visited[npos] = 1;
				q.push({ start, npos, dis + path[pos][j].second });
			}
		}
	}

	cout << answer;
}

void solve()
{
	input();
	solution();
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solve();
	return 0;
}

결과

리프노드 방문 체크를 다시 해준 코드랑 안 해준 코드랑 시간이 거의 두 배 차이가 난다!
근데 정석풀이는 훠어어얼씬 빠르므로 그냥 이런 풀이도 있다 생각하고 정석 풀이로 풀자~