[C++]백준 31477번: 양갈래 구하기

문제출처

풀이방법
DFS사용하였다. 시작 노드인 1에 인접한 모든 노드를 DFS로 탐색한다. edge의 개수가 1인 node를 만나면 연결된 edge의 가중치를 return한다. 이때 edge의 개수가 1이 아닌 직전 node에선 edge의 개수가 1인 노드로부터의 모든 가중치와 자신의 직전node와 비교하여 더 작은 값을 리턴함으로써 그 경로에 대한 최솟값을 반환하게 된다.

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<vector<ii>> room(N + 1, vector<ii>());
	vector<bool> visit(N+1, 0);
	visit[1] = 1;
	for ( int i = 0; i < N - 1; i++ ) {
		int A, B, V;
		cin >> A >> B >> V;
		room[A].emplace_back(ii(B, V));
		room[B].emplace_back(ii(A, V));
	}
	int total = 0;
	for ( ii x : room[1] ) {
		int d = x.first;
		total += DFS(room, visit, d);
	}

	cout << total << endl;


	return 0;
}

간단한 DFS이다.

#include<iostream>
#include<vector>

using namespace std;

typedef pair<int, int> ii;

int DFS(vector<vector<ii>> &room, vector<bool> &visit, int i) {
	int tmp = 0;
	int edge = 0;
	visit[i] = 1;
	if ( room[i].size() == 1 ) {
		return room[i].front().second;
	}
	for ( ii x : room[i] ) {
		int d = x.first;
		int w = x.second;
		if ( visit[d] == 1 ) {
			edge = w;
			continue;
		}
		tmp += DFS(room,  visit, d);
	}
	tmp = min(tmp, edge);
	return tmp;
}

edge가 1개이면 바로 가중치를 return하고 그게 아니라면 연결된 edge중 이미 방문한 node와 연결된 edge를 제외한 모든 edge로부터 계산된 가중치를 합하여 이를 이미 방문한 node와 연결된 edge의 가중치와 비교하여 더 작은 값을 return한다.