[BOJ알고리즘, C++]#16437_양 구출 작전, 트리, 재귀 DFS

#1. 문제

https://www.acmicpc.net/problem/16437

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

트리 자료구조는 1:n 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 그래프의 한 종류로 노드와 간선으로 이루어져 있으며, 계층 구조를 이룹니다. 더불어, 트리 자료구조는 순환 구조를 갖지 않으며, 두 임의의 노드 사이의 경로는 유일합니다.

 

2. DFS

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 출발 노드로부터 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. 일반적으로, 깊이 우선 탐색은 재귀 호출 혹은 스택 자료구조를 활용하여 구현합니다.

 

3. 노드 별 양(양수), 늑대(음수) 값 기억하고, 루트 노드에 최종 값을 모으자!

1. 먼저, 2차원 vector 컨테이너를 구성하고, 별도의 배열 선언하여 각 노드 별 양 혹은 늑대 수를 기억합니다. 이때, 어떤 노드가 '양'을 가질 경우 그 값을 양수로 저장하고, '늑대'일 경우 음수로 저장합니다.
2. 루트 노드(1번 노드)를 시작으로 재귀 DFS를 정의합니다. 이때, 다음 노드들의 결과 값을 저장할 때 max(0LL, dfs(next))를 통해 결과 값이 음수가 되는 것을 방지합니다. 왜냐하면, 다음 노드에 올라갈 양의 수가 음수가 될 수 없기 때문에, 늑대의 수가 양의 수보다 클 경우, 단순히 0 값을 결과 값으로 설정해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/16437
    @문제: N개 노드로 이루어진 트리에서 1번 노드에 도착 할 수 있는 양의 수
    @설명
        1. 재귀 dfs 활용
        2. 늑대의 수 > 양의 수가 될 경우, 총 결과 값이 음수가 됩니다. 이를 0으로 처리해주는 작업 필요합니다!
*/


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

typedef long long ll;
#define MAX 123457

int N;
vector<int> tree[MAX];
ll animals[MAX];

ll dfs(int cur)
{
    ll result = animals[cur];

    for(const auto& next : tree[cur])
    {
        result += max(0LL, dfs(next));
    }

    return result;
}

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

    cin >> N;

    //@트리 구성
    for(int i=2; i<=N; ++i)
    {
        char t;
        int a, p;

        cin >> t >> a >> p;
        tree[p].push_back(i);
        animals[i] = (t == 'W')? -a : a;
    }

    //@dfs
    cout << dfs(1);

    return 0;
}

 

---