취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15805번 문제인 트리 나라 관광 가이드이다.
문제는 아래 링크를 확인하자.

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

지문의 첫 문단 서술이 애매해 보충설명하면, 윤호가 구성한 패키지의 도시 방문 순서는 "트리의 모든 도시를 방문하는 가장 짧은" 이동경로임이 보장된다. 즉, 주어지는 경로는 처음 주어지는 노드를 루트로 갖는 모양의 트리에서의 dfs 방문 순서와 같게 된다.

dfs 과정에서 언제 탐색을 퇴각(backtrack)하는지를 생각하며 잘 구현해보자. 스택을 이용하면 편하게 구현할 수 있다.

이러한 이동 과정에서 트리의 모든 에지는 양 방향으로 한 번씩 이용해야하므로, 전체 노드의 개수는 dfs 경로의 길이를 이용해 계산해낼 수 있다.

아래는 제출한 소스코드이다.

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

vector<int> stk;
int ans[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	stk.emplace_back(-1);
	stk.emplace_back(-1);
	int idx = 0;

	int N; cin >> N;
	int NN = (N + 1) / 2;

	N--;
	int x; cin >> x;
	ans[x] = -1;
	stk.emplace_back(x);
	idx++;
	
	while (N--) {
		cin >> x;
		if (x == stk[idx]) {
			ans[stk.back()] = stk[idx];
			stk.pop_back();
			idx--;
		}
		else {
			stk.emplace_back(x);
			idx++;
		}
	}

	cout << NN << '\n';
	for (int i = 0; i < NN; i++) cout << ans[i] << ' ';
}