[BOJ 24935 // C++] Travelling Caterpillar

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

 

이번에 볼 문제는 백준 24935번 문제인 Travelling Caterpillar이다.
문제는 아래 링크를 확인하자.

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

24935번: Travelling Caterpillar

0번 노드에서 Lilith가 먹어야하는 잎이 있는 노드까지의 경로를 이루는 에지들은 무조건 2회(잎 방향, 0번 노드 방향) 이상을 경유하게 된다. 그 외의 에지들은 전혀 경유할 필요가 없다.

 

이때, 위의 경유하게 되는 에지들을 DFS순으로 따라 이동하면 모든 잎이 있는 노드를 방문하면서 각 에지들을 정확히 두 번씩만 방문하는 경로를 얻을 수 있다. 이때의 움직인 경로의 길이가 문제에서 구하는 최솟값임은 명백하다.

 

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

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

vector<pair<int,int>> G[1000]; // {노드, 가중치}
bool munch[1000];

pair<int, bool> dfs(int cur, int par) {
	int ret = 0;
	bool chk = 0;
	for (auto p : G[cur]) {
		int node = p.first;
		if (node == par) continue;
		auto tmp = dfs(p.first, cur);
		if (munch[node] || tmp.second) {
			chk = 1;
			ret += tmp.first + p.second;
		}
	}

	return make_pair(ret, chk);
}

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

	int N, K; cin >> N >> K;
	for (int i = 1; i < N; i++) {
		int x, y, d; cin >> x >> y >> d;
		G[x].emplace_back(make_pair(y, d));
		G[y].emplace_back(make_pair(x, d));
	}

	while (K--) {
		int x; cin >> x;
		munch[x] = 1;
	}

	cout << dfs(0, 0).first * 2;
}