골드3 - 백준 12896 스크루지 민호

백준 12896 스크루지 민호

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

접근방법

트리로 이루어진 도시들 사이에서 최적의 위치에 소방서가 건설되기 위해서는 트리의 지름을 구하고 그 중간의 위치에 소방서를 지어야한다. 트리의 지름이 딱 절반으로 나누어지면 몫을 출력하고 절반으로 나누었을때 나머지가 있다면 몫에 +1을 해준다.

풀이

트리의 지름을 구하기 위해서 임의의 한 지점에서 가장 먼 지점을 구하고 그 지점에서 가장 먼 지점까지의 거리를 구하면 트리의 지름을 구할 수 있다.
우선 1번 도시에서 dfs를 이용해서 dis 변수의 first에 가장 먼 거리를 갱신해주면서 second에 해당 도시를 저장해주었다. dis와 visited 배열을 초기화 해주고 가장 먼 도시를 기준으로 다시 한번 dfs를 진행하여 가장 먼 거리를 구해준다. dis.first에 저장된 트리의 지름을 2로 나누어서 결과값을 출력해준다.

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> node[100001];
bool visited[100001];
pair<int, int> dis = { -1, 0 };

void dfs(int num, int depth)
{
	if (dis.first == -1 || depth > dis.first)
	{
		dis.first = depth;
		dis.second = num;
	}

	for (int i = 0; i < node[num].size(); i++)
	{
		if (visited[node[num][i]])
			continue;

		visited[node[num][i]] = true;
		dfs(node[num][i], depth + 1);
	}
}

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

	int N;
	cin >> N;

	for (int i = 0; i < N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		node[a].push_back(b);
		node[b].push_back(a);
	}

	dfs(1, 0);
	int temp = dis.second;
	dis = { -1,-1 };
	memset(visited, false, sizeof(visited));
	dfs(temp, 0);
	if (dis.first % 2 == 0)
		cout << dis.first / 2 << endl;
	else
		cout << dis.first / 2 + 1 << endl;
}