문제 이해 단계
https://www.acmicpc.net/problem/1967
문제가 굉장히 복잡하게 쓰여있는데 사실 간단하다.
노드에서 노드로 가는 데에는 각각의 가중치가 존재한다.
이때, 한 트리의 리프(가장 아래에 있는 노드)에서
다른 리프로 가는 경로가 존재할 것이고, 당연히 각각의 가중치가 존재한다.
이때, 한 리프에서 다른 리프로 가는 경로에서
얻을 수 있는 가중치 합 중 가장 큰 가중치 합을 구하는 문제이다.
예시로 된 그림을 보면 더 이해가 간단히 될 것이다.
문제 접근 단계
리프 노드를 알아내기 위해서는 연결된 노드를 계속해서 타고 들어갔을 때,
마지막 노드는 연결된 노드가 없다.
즉, 해당 노드에서 여러 노드가 연결되어 있다면,
갈림길의 경우의 수를 타고 들어가는 합을 모두 구한 후 비교한다.
이 작업을 해주기 위해 DFS를 사용하는 것이 적절하다.
DFS를 사용해서 가중치를 재귀적으로 구한 뒤, 앞에 값과 더한 후,
이전의 값과 비교 후 더 큰 값을 그 노드의 답으로 삼는다.
말을 좀 어렵게 했는데 재귀함수 부분은
문제 구현 단계에서 코드로 정확히 설명하겠다.
문제 구현 단계
int Dfs(int x) {
if (c[x]) return -1000;
int sum = 0;
c[x] = true;
for (int i = 0; i < list[x].size(); i++) {
int node = list[x][i].first;
int value = list[x][i].second;
sum = max(sum, value + Dfs(node));
}
return sum;핵심이 되는 DFS 함수이다.
매개변수로 노드 번호 x를 받는다.
만약 이미 방문한 노드이면 -1000을 반환한다.
그 이유는 밑에 sum = max(sum, value + Dfs(node));
에서 만약 방문한 노드일 경우 0으로 처리하면
value가 sum보다 높을 경우가 발생할 수 있어서, 의도하지 않은 값이 더해질 수가 있다.
그래서 문제에서 간선의 가중치의 최댓값이 100이기 때문에
-1000을 반환하면 절대로 sum보다는 커질 수 없다.
방문하지 않은 노드라면 sum = 0, 방문 처리를 한다.
그 노드와 연결된 노드와 가중치를 모두 가져와서
가중치+DFS(연결된 노드)와 같은 노드에서 돌린 이전의 DFS를 비교하여
더 큰 값을 답으로 삼는다.
이 과정을 반복하다 보면 가중치의 최댓값을 얻을 수 있다.
밑에 전체코드에 대한 설명을 한 후 코드 설명을 끝내겠다.
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int,int>> list[10001];
bool c[10001] = { false };
int Dfs(int x) {
if (c[x]) return -1000;
int sum = 0;
c[x] = true;
for (int i = 0; i < list[x].size(); i++) {
int node = list[x][i].first;
int value = list[x][i].second;
sum = max(sum, value + Dfs(node));
}
return sum;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int v1, v2, v3;
cin >> v1 >> v2 >> v3;
list[v1].push_back(make_pair(v2, v3));
list[v2].push_back(make_pair(v1, v3));
}
int answer = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) c[j] = false;
answer = max(answer,Dfs(i));
}
cout << answer;
}노드를 담을 list배열과, 그 안에 연결된 노드, 가중치 값을 저장해 뒀다.
그리고 첫 번째 노드부터 끝까지
한 번씩 전부 DFS를 돌린 후, 가장 큰 값을 정답으로 처리한다.
시행착오
역시 난 DFS 구현에 약한 것 같다.
DFS로 푸는 문제인 건 바로 알아챘지만, 구현하는 데는 오래 걸렸다.
DFS 관련 문제는 앞으로도 좀 많이 풀어봐야겠다.
재귀함수는 막상 짜보면 코드는 몇 줄 안 나오는데 머리가 터질 것 같다.
이게 좀 열받더라. 진짜 많이 풀어봐야겠다. 거의 기출 같다.