백준 18126 너구리 구구

백준 18126 너구리 구구

---

• 오늘은 너구리 구구 문제를 풀었다. 알고리즘 스터디에서 분류가 트리였는데, 트리 문제를 어떤 식으로 풀어야 할 지 몰라서 그냥 DFS 로 풀었다.
• 맨날 풀던 DFS 문제처럼 단순하게 생각하면, 말단 리프 까지 도달했을 때의 경로의 합이 가장 큰 것을 출력하기만 하면 되는 거였다. 다 풀었는데, 계속 틀렸다고 나왔다.

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int,long long>> v[5002];
int visited[5002] = {0,};
long long max_val = 0;

void dfs(int x, long long p)
{
    for (int i = 0; i < v[x].size(); i++)
    {
        if (visited[v[x][i].first] == 0 )
        {
            visited[v[x][i].first] = 1;
            dfs(v[x][i].first, p + v[x][i].second);
        }
    }
    max_val = max(max_val, p);
    return;
}

int main()
{
    int n;
    cin>>n;
    for (int i =0; i < n-1; i++)
    {
        int a,b;
        long long c;
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    //visited[1] = 1;
    dfs(1, 0);
    cout<< max_val<<"\n";
    return 0;
}

이게 틀린 코드 였는데, 첫번째 시작점을 방문체크를 안해서 방문한 지점을 한 번 더 거치는 경우가 나왔던 거였다. 사실 단순한 DFS 문제였는데 오랜만에 풀고 기억이 가물가물해서 이렇게 실수를 한 거 같다.

저 문제에서 주석 처리된

visited[1] = 1;

만 다시 주석을 풀어주면 문제가 쉽게 해결된다! WOW