백준 15386번 Birokracija

문제 링크입니다: https://www.acmicpc.net/problem/15368

다단계의 현실을 간접적으로 보여주는 재미있는 문제였습니다.

DFS(Depth First Search) 알고리즘을 이용하여 푸는 문제였습니다.

처음에는 문제를 그대로 구현하여 DFS를 20만번이나 하는 어마무시한 코드를 작성해서 메모리 초과가 발생했습니다.

이후에는 세진님(http://sejinik.tistory.com/96#comment12977181) 코드를 참고하여 풀었습니다.

알고리즘은 아래와 같습니다.

1. 양방향 그래프처럼 입력받고 i의 상사가 누군지 표시합니다.

2. DFS를 이용하여 트리를 형성하고 미리 num의 자식의 수를 employee 배열에 표시합니다.

3. 이후에는 또 다시 DFS를 이용하여 급여를 계산합니다.

-> 자식의 수를 그대로 받고 나의 자식 수를 더하면 급여 계산 끝!

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 200000 + 1;

 

int N;

int boss[MAX], employee[MAX];

vector<int> graph[MAX];

long long payment[MAX];

 

//리프부터 루트까지 계속 1씩 증가시킨다

int calcCoin(int num)

{

        int coin = 0;

 

        for (int i = 0; i < graph[num].size(); i++)

                 if (graph[num][i] != boss[num])

                         coin += calcCoin(graph[num][i]);

 

        //자식의 수 업데이트

        employee[num] = coin;

        return coin + 1; // 리프 포함

}

 

void DFS(int num)

{

        //나 자신(1부터 시작)

        payment[num] = 1;

       

        for (int i = 0; i < graph[num].size(); i++)

                 if (graph[num][i] != boss[num])

                 {

                         DFS(graph[num][i]);

                         //자식 수만큼 더해준다

                         payment[num] += payment[graph[num][i]];

                 }

 

        //고용 인원 누적만큼 더해준다

        payment[num] += (long long)employee[num];

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 2; i <= N; i++)

        {

                 int num;

                 cin >> num;

 

                 graph[i].push_back(num);

                 graph[num].push_back(i);

                 boss[i] = num;

        }

       

        calcCoin(1);

        DFS(1);

 

        for (int i = 1; i <= N; i++)

                 cout << payment[i] << " ";

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~