[백준/BOJ] 25924 Darkest Dungeon C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/25924

[설명]
문제의 조건을 보면 문제의 그래프는 트리임을 알 수 있다. 이때, 통로를 K번 이하로 통과할 수 있다는 조건이 있다. 이에 대하여 “트리의 지름”을 기준으로 생각해볼 수 있다. 트리의 지름이란 트리에서 두 정점을 골라 거리를 잰다고 했을 때, 가장 거리가 먼 경우를 의미한다. 이 문제의 경우, 거리는 통로의 개수로 생각할 수 있다.

따라서 만약 트리의 지름에 대한 경로와 K를 비교해 지름 경로의 통로 수가 더 크다면 지름 경로를 지나도록 하여 K 이하가 되게 출력하면 된다. 하지만 K가 더 크다면 중간에 트리의 지름이 아닌 경로의 노드들을 추가해야 한다. 이때, 다른 노드로 가면 다시 돌아와야 하므로 통로 수는 2씩 증가하며 다시 돌아올 노드도 추가해주어야 한다.

[코드]

#include<iostream>
#include<vector>
using namespace std;

vector<int> graph[500001], ans;
int dis[500001], point[2], comp;
bool visited[500001], path[500001];

void dfs(int start, int cnt, int check) {
	dis[start] = cnt;
	if (comp < cnt) {
		comp = cnt;
		point[check] = start;
	}
	visited[start] = 1;
	for (auto iter = graph[start].begin(); iter != graph[start].end(); iter++) {
		if (visited[*iter]) continue;
		dfs(*iter, cnt + 1, check);
	}
	visited[start] = 0;
}

void find_path(int start, int end) {
	if (start == end) {
		path[start] = 1;
		return;
	}
	visited[start] = 1;
	for (auto iter = graph[start].begin(); iter != graph[start].end(); iter++) {
		if (visited[*iter]) continue;
		find_path(*iter, end);
		if (path[*iter]) path[start] = 1;
	}
	visited[start] = 0;
}

void ans1(int start, int cnt) {
	cout << start << '\n';
	if (cnt == 0) return;
	visited[start] = 1;
	for (auto iter = graph[start].begin(); iter != graph[start].end(); iter++) {
		if (visited[*iter]) continue;
		if (path[*iter]) ans1(*iter, cnt - 1);
	}
	visited[start] = 0;
}

void ans2(int start) {
	ans.push_back(start);
	if (!path[start]) comp--;
	int next = -1;
	visited[start] = 1;
	for (auto iter = graph[start].begin(); iter != graph[start].end(); iter++) {
		if (visited[*iter]) continue;
		if (!path[*iter] && comp) {
			ans2(*iter);
			ans.push_back(start);
		}
		if (path[*iter]) next = *iter;
	}
	if (next != -1) ans2(next);
	visited[start] = 0;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, K, i, a, b; cin >> N >> K;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(1,0,0);
	comp = 0;
	dfs(point[0], 0, 1);
	find_path(point[0], point[1]);
	if (K <= dis[point[1]]) {
		cout << K + 1 << '\n' << K << '\n';
		ans1(point[0], K);
	}
	else {
		comp = (K - dis[point[1]]) / 2;
		ans2(point[0]);
		int l = ans.size();
		cout << dis[point[1]] + 1 + (l - dis[point[1]] - 1) / 2 << '\n' << l - 1 << '\n';
		for (auto iter = ans.begin(); iter != ans.end(); iter++) cout << *iter << '\n';
	}
}