BaekJoon 1167번: 트리의 지름

트리의 지름을 구하는 알고리즘이다.

BFS를 써서 문제를 해결하고자 했으나 마땅한 방법이 생각나지 않아 다른 블로그의 힘을 빌렸다.

blog.myungwoo.kr/112

트리의 지름 구하기

풀이법

1) 아무 노드 a (이 코드의 경우 1)를 이용해서 a에서 가장 먼 점인 x를 구한다.

2) x에서 가장 먼 노드인 y를 구하고 x-y 간의 거리를 구한다. (지름 구하기)

3) BFS를 이용하여 vistied 배열과 dist 배열을 사용하여 문제를 해결한다. 이 때 초기화를 잊지 말자

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

int n;
vector<pair<int,int>>arr[INF];
bool visited[INF];
int dist[INF];
int maxIndex, maxNum;
int distance(int num)
{
	for (int i = 1; i <= n; i++)
	{
		dist[i] = 0;
	}
	queue<pair<int, int>> q;
	q.push({ num,0 });
	visited[num] = true;
	while(!q.empty())
	{
		int now = q.front().first;
		int cnt = q.front().second;
		
		q.pop();
		for (int i = 0; i < arr[now].size(); i++)
		{
			int next = arr[now][i].first;
			int weight = arr[now][i].second;
			if (!visited[next])
			{
				q.push({ next,cnt + 1 });
				dist[next] = dist[now] + weight;
				visited[next] = true;
			}
		}
	}
	maxNum = 0;
	maxIndex = 0;
	for (int i = 1; i <= n; i++)
	{
		if (maxNum < dist[i])
		{
			maxNum = dist[i];
			maxIndex = i;
		}
	}
	return maxIndex;

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b,c;
		cin >> a >> b>>c;
		arr[a].push_back({ b,c });
		while (b != -1)
		{
			cin >> b;
			if (b == -1)
				break;
			cin >> c;
			arr[a].push_back({ b,c });
		}
	}
	memset(visited, false, sizeof(visited));
	int x = distance(1); //1 기준으로 가장 먼 것.
	memset(visited, false, sizeof(visited));
	int y = distance(x); // 1에서 가장 먼 x 기준 제일 먼 y
	cout << maxNum;
}

한계점 및 개선사항

시간이 부족하다는 것은 문제에 대해 깊이 있게 이해를 못했다는 방증이라고 생각한다. 조금 더 집중해서 문제를 풀 수 있도록 노력해야 할 것이다. 추가적으로 memset을 cstring 헤더 없이 사용하면 컴파일 에러가 발생한다. 잊지 않고 cstring 헤더를 선언해야 한다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest

solved.ac/profile/pearlcrum