본문 바로가기

Problem Solving/Baekjoon OJ

[BOJ 12784] 인하니카 공화국

 

12784번: 인하니카 공화국

인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들

www.acmicpc.net

 

이 문제와 정확히 일치하는 문제를 GCC 출제 큐에 push하고 나서 반나절 뒤에 트리 디피 문제를 찾아 풀다가 우연히 발견했다. AC를 받기 전까지 제발 내 착각이기를 빌었다.. 흔한 유형이라 비슷한 문제가 있을 거라고 생각하기는 했지만, 아쉬운 것은 어쩔 수 없다.

 

풀이

 

루트와 리프를 연결하는 경로가 없도록 만들 때, 자르는 간선의 가중치의 합이 최소가 되게 하는 문제다.

이는 dfs를 돌면서 트리의 정점에 대한 dp를 해결하면 된다.

$dp[u]=\sum min(val,dp[v])$ 이고, $v$ 가 리프일 때를 따로 처리해줘야 한다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> ad[1001];
int dfs(int u,int p) {
	int ret=0;
	for(auto &[v,d] : ad[u]) if(v^p){
		int k=dfs(v,u);
		ret+=k?min(d,k):d;
	}
	return ret;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int tc; cin >> tc;
	while(tc--){
		int n,m; cin >> n >> m;
		for(int i=1;i<=n;i++) ad[i].clear();
		while(m--){
			int u,v,d; cin >> u >> v >> d;
			ad[u].push_back({v,d});
			ad[v].push_back({u,d});
		}
		cout << dfs(1,0) << '\n';
	}
}

'Problem Solving > Baekjoon OJ' 카테고리의 다른 글

First Solve 3개  (0) 2021.11.16
[BOJ 1167] 트리의 지름  (0) 2021.10.24
[BOJ 12784] 인하니카 공화국  (0) 2021.10.19
[BOJ 16998] It’s a Mod, Mod, Mod, Mod World  (0) 2021.10.17
Ruby V  (3) 2021.08.31
Class 9  (4) 2021.08.29