boj, 백준) 12784. 인하니카 공화국 (C/C++)

1. 문제 링크

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

12784번: 인하니카 공화국

2. 문제 개요

인하니카 공화국은 1번 ~ N번까지 N개의 섬으로 이루어진 나라이다. 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다.

 

1번 섬을 제외한 다리가 하나밖에 없는 어느 섬에서 유명한 연쇄 살인마 괴도 루팡이 자신의 목숨을 노리고 있다.

몇 개의 다리를 폭파하여, 루팡이 있을 가능성이 있는 모든 섬에서 자신의 섬으로의 모든 경로를 차단하려고 한다. 각 다리를 폭파하려면 다리의 크기에 따라 다이너마이트의 개수가 다르다. 다이너마이트는 매우 비싸기 때문에 진은 사용하는 다이너마이트의 개수를 최소화하고 싶어 한다. 각 섬을 연결하는 다리를 폭파하기 위한 다이너마이트의 개수가 주어졌을 때, 진을 도와 필요한 최소 다이너마이트의 개수를 구하라.

 

 

3. 문제 힌트

Tree의 정의를 잘 생각해보자.. acyclic connected graph... 두 섬을 연결하는 다리를 최소한의 개수로.... (문제를 잘 읽어보자)

 

문제가 조금 헷갈리게 써져있어서 이해하는데 오래 걸렸다.. 1번 섬을 제외한 다리가 하나밖에 없는 어느 섬 -> 리프 노드를 의미한다.

리프 노드에서 1번(루트라고 가정)까지 거슬러오면서 가장 저렴한 구간을 선택하면 된다.

 

4. 문제 풀이

문제를 어떻게 풀면 좋을까~ 좋을까~ 하다가  리프 노드에서부터 루트까지 최솟값을 가지고 거슬러 올라오면 되는 것이었다.

 

주어지는 그래프는 무조건 Tree이다. 문제의 정의에 의해서 모든 섬을 연결하는데 최소한의 간선(다리)를 사용했기 때문. 그래서 cycle이 없다.

첫 번째 제출 때 cycle까지 판별하는 것도 구현했는데 문제를 다시 읽어보니 트리만 입력으로 주어졌다....

 

문제에서는 1번을 루트라고 암시하고 있다.

그럼, 자식들의 자식들의 자식... 을 계속 내려가다 보면 리프 노드(루팡)가 나오는데, 그때부터 다시 부모로 리턴하면서 올라간다.

 

부모(서브 트리의 루트) 노드는 여기서 선택을 할 수 있는데, 자식들을 다 자를 것인지, 자신을 자를 것인지이다.

 

출처 : 백준 12784문제 그림

위 그림에서 2번 노드를 기준으로 했을 때, 자신의 부모와 연결된 2-1간선을 자를 것인지,

3-2, 4-2간선을 자를 것인지 선택해야 한다.

 

그래서 각 노드별로 자신의 부모와 연결된 노드 vs 자식들의 합을 비교해야 하는 것.

 

리프 노드에서부터 최솟값을 가지고 계속 올라온다.

DP라고 할 수 있는 부분은 항상 최솟값(보장됨)을 가지고 가는 점과, 루트 - 서브 트리들 - 서브 트리들 - 서브 트리들로 계속 똑같은 문제를 풀어나간다는 점이라고 할 수 있겠다.

 

위 그림에서도 왼쪽 같은 경우, 2번 노드 기준으로 min(1, 4+1)이라서 자신의 부모와 연결된 간선을 선택했고,

오른쪽은 min(4, 1+2)로 자식들을 모두 자르는 것이 이득이기 때문에 자식들을 다 잘랐다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int t;
struct Edge {
	Edge(){}
	Edge(int to_, int weight_) :to(to_), weight(weight_) {}
	int to;
	int weight;
};
vector<vector<Edge>> adj;
vector<bool> visited;

int dfs(int cur, int before)
{
	int ret = 0, beforeWeight = 0;

	for (Edge next : adj[cur])
	{
		if (next.to == before) {
			beforeWeight = next.weight;
			continue;
		}

		if (visited[next.to] == false) {
			visited[next.to] = true;
			ret += dfs(next.to, cur);
		}
	}

	if (adj[cur].size() == 1)
		return beforeWeight;


	if (ret == 0)
		return 0;
	else
		return min(ret, beforeWeight);
}
int main()
{
	scanf("%d", &t);

	while (t--)
	{
		int n, m;
		scanf("%d %d", &n, &m);

		adj = vector<vector<Edge>>();
		adj.resize(n + 1);

		visited = vector<bool>();
		visited.resize(n + 1, false);

		for (int i = 0; i < m; ++i)
		{
			int from, to, weight;
			scanf("%d %d %d", &from, &to, &weight);

			adj[from].push_back(Edge(to, weight));
			adj[to].push_back(Edge(from, weight));
		}

		int ans = 0;

		for (Edge next : adj[1])
			ans += dfs(next.to, 1);

		printf("%d\n", ans);
	}

	return 0;
}

6. 결과