[C++][백준 12784] 인하니카 공화국

문제

접근 방법

1번섬을 제외한 다리가 하나밖에 없는 어느 섬

해당 섬은 가장 끝에 존재하는 섬을 의미합니다.
즉 리프 노드입니다.

예제에서 보여주듯 양옆에 존재하는 리프 노드가 루트와 연결되지 않게 다리를 제거해 줘야 합니다.
리프 노드에서 루트까지 존재하는 다리를 끊는 경우 중 제일 적은 다이너마이트를 사용하는 경우를 찾아내면 됩니다.

코드

#include <iostream>
#include <vector>
using namespace std;
using pii = pair<int, int>;
#define SIZE 1001
#define INF 987654321

int T, N, M;
vector<pii> graph[SIZE];
bool isVisited[SIZE];

int dfs(int cur)
{
    isVisited[cur] = true;

    int sum = 0;

    for (pii nextNode : graph[cur])
    {
        if (isVisited[nextNode.first])
        {
            continue;
        }

        int nextValue = dfs(nextNode.first);

        nextValue = min(nextValue, nextNode.second);

        sum += nextValue;
    }

    return sum == 0 ? INF : sum;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> T;

    while (T--)
    {
        cin >> N >> M;

        for (int i = 1; i <= N; ++i)
        {
            isVisited[i] = false;
            graph[i].clear();
        }

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

            graph[a].push_back({b, d});
            graph[b].push_back({a, d});
        }

        cout << (N == 1 ? 0 : dfs(1)) << "\n";
    }
    return 0;
}

풀이

현재 노드에서 연결된 다리를 끊거나 자식 노드에서 연결된 다리를 모두 끊는 방법 중 하나를 택합니다.
자식 노드에서 연결된 다리를 모두 끊는 과정 또한 자식 노드에서 연결된 다리를 끊거나 자식의 자식 노드에서 연결된 다리를 모두 끊는 방법을 선택할 수 있습니다.

즉 재귀적인 구조를 지니고 있기에 재귀 함수를 활용하여 가장 최소인 값을 구해주면 됩니다.

N이 1인 경우에는 루팡이 존재할 섬이 없기에 0을 반환하면 됩니다.