백준 18126번 '너구리 구구' DFS 및 자료구조 적용 해결기

#백준문풀 #스파르타코딩 #DFS #트러블슈팅

✨ Written with Gemini 2.5 Flash

KEY POINT

무방향 그래프 == 양방향 간선!

문제 상황

백준 18126번 "너구리 구구" 문제에 도전했다. 최단 거리가 아닌 최장 거리를 구하는 문제였고, 예시 입력을 통해 그래프가 사이클이 없는 트리 형태라는 것을 파악했다. BFS와 DFS 중에 최장거리를 구하기 위해 DFS를 택했다.

초기 접근법과 문제점

이 문제의 요구사항은 1번 방에서 출발하는 최장 거리를 구하는 것이었다. 간선에 가중치가 있으므로 최단 거리를 구하는 BFS는 적합하지 않다고 판단했고, 시작 정점에서 경로를 끝까지 탐색하는 DFS를 사용하기로 결정했다.

1차 시도: DFS 구현의 난관

2차 시도: for문 오류와 자료구조 선택 미스

vector<pair<int, long>> adj(5001); 
...
for (const auto& edge : adj[curIdx]) {
    ...
}

근본 원인 분석

위의 오류들을 해결하고 제출했지만, "틀렸습니다" 가 떴다.
문제의 근본적인 원인은 main 함수 내에 있었다.

최종 해결: 양방향 매핑

핵심 아이디어

무방향 그래프의 특성을 반영하여 간선을 양쪽 방향에 모두 저장하는 양방향 매핑을 구현했다.

adj[u].push_back({ v, w });
adj[v].push_back({ u, w });

이렇게 하면 1번 정점이 입력의 첫 번째에 오든, 두 번째에 오든 adj[1]에는 항상 연결된 모든 정점 정보가 담기게 된다.

제출한 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

long long maxDist = 0;

void dfs(int curIdx, int prevIdx, long long totalDist, const vector<vector<pair<int, int>>>& adj) {
    for (const auto& edge : adj[curIdx]) {
        int nextIdx = edge.first;
        int weight = edge.second;

        if (nextIdx == prevIdx) {
            continue;
        }

        dfs(nextIdx, curIdx, totalDist + weight, adj);
    }

    if (totalDist > maxDist) {
        maxDist = totalDist;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<vector<pair<int, int>>> adj(N + 1);

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        int w;
        cin >> u >> v >> w;

        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }

    dfs(1, 0, 0, adj);

    cout << maxDist << '\n';

    return 0;
}

핵심 레슨런

  1. 그래프의 함정: 무방향 그래프 문제를 풀 때는 간선을 양쪽 방향에 모두 저장하는 것을 잊지 말아야 한다. 단방향으로만 저장하면 탐색이 불완전해져 틀린 답이 된다.
  2. 자료구조 선택: 문제의 특성을 파악하여 올바른 자료구조를 택하는 능력이 중요하다. 정점 번호가 순차적일 때는 vector를 사용하는 것이 효율적이다. 굳이 복잡하게 map을 사용할 필요가 없다.
  3. DFS 구현: 재귀 호출 시 prevIdx와 같은 인자를 활용해 불필요한 역방향 탐색을 막는 것이 중요함을 배웠다. DFS의 동작 방식을 정확히 이해하지 못하면 작은 실수 하나로 코드가 꼬여버릴 수 있다.

결론

이번 문제를 통해 그래프 탐색 문제에서 가장 기초적인 '양방향 매핑'의 중요성을 다시 한번 깨달았다.
코테는 누구나 공부하면 터득하는 알고리즘 지식 뿐만 아니라 문제의 세부 사항(그래프의 방향성, 자료구조의 특성 등)을 꼼꼼하게 파악하는 능력이 정말 중요하다고 생각했다.
다음부터 그래프 탐색 문제를 읽을 때는 그래프의 특성부터 확실히 체크해야겠다.