백준 18126 - 너구리 구구(C++)

문제 링크입니다. https://www.acmicpc.net/problem/18126

18126번: 너구리 구구

DFS를 이용해 푸는 문제입니다. 다익스트라 알고리즘으로도 풀 수 있겠지만 비추천합니다.

1번에서 시작해 가장 가중치가 큰 곳의 값을 구하는 문제입니다.

항상 시작은 1번이니 1번부터 시작해 DFS 탐색을 해줍니다.

 

재귀함수를 반복할 때마다 최대 거리를 비교하면서 탐색이 끝난 뒤에 최대 거리를 출력해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N;
vector<pair<int, int>> line[5001];
int check[5001];
long long int max_cost;

void dfs(int start, long long int cost) {
	check[start] = 1;
	max_cost = max(max_cost, cost);
	for (int i = 0; i < line[start].size(); i++) {
		int x = line[start][i].first;
		if (check[x] == 0) {
			check[x] = 1;
			dfs(x, cost + line[start][i].second);
		}
	}
}

void solve() {
	dfs(1, 0);
	cout << max_cost;
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		line[x].push_back({ y,cost });
		line[y].push_back({ x,cost });
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요