[Algorithm] 백준 - 트리의 기둥과 가지 (20924번)

문제

[백준] 트리의 기둥과 가지
(Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Winter Algorithm Camp Contest > 초급 E번)

사용 알고리즘

- 깊이 우선 탐색 (DFS)

해결방법

• 루트노드가 주어지므로, 루트노드부터 DFS 탐색
  • 기가노드를 만난 경우 => 기둥의 길이 도출 (gi_len)
  • 리프노드를 만난 경우 => 가지의 길이 도출 (ga_len)
• 예외 케이스
  • 루트노드가 기가노드인 경우
    = 기둥 길이는 0
  • 기가노드가 리프노드인 경우 (사실상 기가노드가 존재하지 않는 경우)
    = 가지 길이는 0
• 반례 케이스
  기가노드가 루트노드인 경우, 2개의 자식을 가지는 노드 3번이 기가노드로 체크될 수 있다. 이 부분을 유의해서 풀었음
  Input 
  5 2
  1 2 3
  2 3 4
  3 4 1
  3 5 2
  
  Output
  0 6

 

소스코드

사용언어 : c++

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<pair<int, int>>> vec;

int N, R;
int visited[200001];
int giga_node, gi_len, ga_len;

void dfs(const vec& v, int n, int len)
{
    if (visited[n]) return;

    visited[n] = 1;

    // 기가노드를 만난 경우
    if (giga_node == 0 && v[n].size() > 2) {
        giga_node = n;
        gi_len = len;
        len = 0;
    }

    // 리프노드를 만난 경우
    if (v[n].size() == 1) {
        ga_len = max(ga_len, len);
    }

    for (const auto& edge : v[n]) {
        int next_node = edge.first;
        int weight = edge.second;

        dfs(v, next_node, len+weight);
    }
}

int main ()
{
    cin >> N >> R;

    vec grph(N+1);

    for (int i=0; i<N-1; i++) {
        int a, b, d;
        cin >> a >> b >> d;

        grph[a].push_back(make_pair(b, d));
        grph[b].push_back(make_pair(a, d));
    }

    if (grph[R].size() > 1) { // 루트노드 == 기가노드인 경우
        giga_node = R;
    }

    dfs(grph, R, 0);
    
    if (giga_node == 0) { // 기가노드 == 리프노드인 경우
        gi_len = ga_len;
        ga_len = 0;
    }

   cout << gi_len << " " << ga_len;

    return 0;
}

함수의 파라미터로 벡터가 들어갈 때

* void dfs(const vec& v, int n, int len)
* & 참조를 함으로서 불필요한 복사가 일어나지 않음

* const를 사용해 벡터 원본 데이터가 변경되지 않도록 하였음

 

한줄평

오랜만에 DFS 문제를 풀었는데, 자꾸 75%에서 틀렸습니다 나와서 당황스러웠다. 위에서 썼듯이 기가노드를 따로 저장안하고 알고리즘을 짠게 문제였다. dfs 호출 전에 루트노드가 기가노드인지 체크하는 부분을 넣었더니 통과되었다! (happy)