[C++] 백준 - 12784 인하니카 공화국

1. 문제 

2. 입출력

3. 문제 해설

이 문제는 DFS 중에서 Leaf 노드를 판별하고 리프노드의 전체 합과 자신을 비교해 잘라주면서 돌아오면 되는 문제이다. 

 

따라서 나는 다음과 같이 해결했다. 우선 다리가 양방향 다리이므로 그래프는 양방향으로 설정해주었다. 

	for (int j = 0; j < M; j++) {
		int s, e, c;
		scanf("%d %d %d", &s, &e, &c);
		AL[s].push_back({ e,c });
		AL[e].push_back({ s, c });
}

그 후 모든 다리를 입력받았을 때 원소의 개수가 1개일 때는 Leaf 노드에 해당한다.

for (int i = 2; i <= N; i++) {
		if (AL[i].size() == 1) {
			isLeaf[i] = 1;
		}
}

그 후 1이 root 노드이므로 1과 연결된 곳에 대해서 깊이 우선 탐색을 수행해준다. 

int ans = 0;
	visited[1] = 1; // 1은 root 노드 
	for (int i = 0; i < AL[1].size(); i++) {
		ans += dfs(AL[1][i].dest, AL[1][i].cost);
}

dfs 로직은 다음과 같다. 

만약 이 노드가 leaf 노드라면 현재의 값을 반환하고 아니라면 방문 표시를 한 후 자신의 자식들의 합과 자신의 다리의 cost를 비교해서 더 작은 것을 더해준다. 

int dfs(int num, int cost) {
	if (isLeaf[num]) return cost;
	int temp = 0;
	visited[num] = 1;

	for (auto bridge : AL[num]) {
		int nn = bridge.dest;
		int ncost = bridge.cost;
		if (visited[nn]) continue;
		temp += dfs(nn, ncost);
	}
	return min(temp, cost);
}

4. 전체 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
int T;
int N, M;
struct bridge {
	int dest;
	int cost;
};
vector<bridge> AL[1001];
bool visited[1001];
bool isLeaf[1001];
int dfs(int num, int cost) {
	if (isLeaf[num]) return cost;
	int temp = 0;
	visited[num] = 1;

	for (auto bridge : AL[num]) {
		int nn = bridge.dest;
		int ncost = bridge.cost;
		if (visited[nn]) continue;
		temp += dfs(nn, ncost);
	}
	return min(temp, cost);
}
int ans;
int main() {

	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d %d", &N, &M);

		for (int j = 0; j < M; j++) {
			int s, e, c;
			scanf("%d %d %d", &s, &e, &c);
			AL[s].push_back({ e,c });
			AL[e].push_back({ s, c });
		}
		for (int i = 2; i <= N; i++) {
			if (AL[i].size() == 1) {
				isLeaf[i] = 1;
			}
		}
		int ans = 0;
		visited[1] = 1;
		for (int i = 0; i < AL[1].size(); i++) {
			ans += dfs(AL[1][i].dest, AL[1][i].cost);
		}
		printf("%d\n", ans);
		for (int i = 1; i <= N; i++) {
			AL[i].clear();
		} // 정리
		memset(isLeaf, 0, sizeof(isLeaf));
		memset(visited, 0, sizeof(visited));
	}
	return 0;
}