ps

99클럽 코테스터디 12일차 TIL 뉴스 전하기

nastorond 2024. 8. 2. 22:45

오늘의 문제 : 뉴스전하기

문제 링크

문제 설명

시간 제한 : 2초
메모리 제한 : 128 MB 
난이도 : Gold ll(BOJ)

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

 

트리구조로 이루어져있는 사원구조에서, 루트부터 각각의 자식 노드를 방문하여 전체 시간이 가장 짧은 것을 찾는 문제로 정리하고 풀이에 들어갔다.

문제 풀이

처음에는 굉장히 단순하게 접근해서 당장의 자식노드가 많은 순서대로 각 루트의 자식 순서를 연결해주고 순서대로 방문하는 풀이로 접근했다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 53

using namespace std;

vector<vector<int>> tree(MAXN);
int dp[MAXN]={0, }, N, par_num, res=0;

bool compare(int a, int b) {
    return tree[a].size() > tree[b].size());
}

void dfs (int par_num, int chd_num) {
    dp[chd_num] = dp[par_num] + 1;

    res = max(res, dp[chd_num]);

    for (int i=0; i<tree[chd_num].size(); i++) {
        dfs(chd_num, tree[chd_num][i]);
        dp[chd_num] += 1;
    }
}

int main () {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++) {
        dp[i] = -1;
    }

    cin >> par_num;
    for (int i=1; i<N; i++) {
        cin >> par_num;
        tree[par_num].push_back(i);
    }
    dp[0] = 0;

    if (N == 1) {
        cout << 0 << "\n";
    }
    else {
        for (int i=0; i<N; i++) {
            sort(tree[i].begin(), tree[i].end(), compare);
        }

        for (int i=0; i<tree[0].size(); i++) {
            dfs(0, tree[0][i]);
            dp[0] += 1;
        }
        cout << res << "\n";
    }

    return 0;
}

dp 에다가 소요한 시간을 기록해 나가면서 풀이했지만 2퍼센트에서 틀렸고,

15
-1 0 0 0 0 2 2 3 3 6 7 7 4 12 13

 

질문게시판에서 찾은 이 반례 또한 통과못해서 문제를 처음부터 다시 접근해봤다.

 

이 반례를 보고 손으로 다시 풀어보니 처음에 접근을 너무 단순하게 해서 틀렸다는 사실을 깨달을 수 있었다.

접근을 아예 잘못해서 풀이를 처음부터 다시 했어야 했는데, 설계하는 과정에서 도저히 풀이가 안되서 결국에는 다른사람의 풀이를 찾아가며 아이디어를 얻어 풀었다.

 

각각의 노드가 자식노드가 몇개있는지 확인하고, 각 노드마다 자식노드의 숫자대로 내림차순 정렬해줬다.

  • 이 문제에서의 핵심이라고 생각되는 부분이 시간을 최소한으로 전부 탐색하려면 자식노드가 많은 부분부터 탐색해야 하는데, 이부분이 좀 헷갈렸었다.
    각각의 노드가 자식이 몇개있는지 전부 확인하고, 그 확인 한 것을 부모노드로 전달하는 방식이다. 굳이 따지자면, 아래에서부터 쌓아서 답을 찾아나가는 Bottom-up 방식을 사용하여 문제를 풀이 한 것 같다.

글을쓰다보니 두서없이 쓴 것 같은데, 정리하자면


다음과 같은 느낌으로 총 소요시간을 측정해줬다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 53

using namespace std;

vector<vector<int>> tree;
int N;

bool compare(int a, int b) {
    return a > b;
}

int dfs (int cur) {
    vector<int> list;

    if (tree[cur].size() == 0) return 0;

    for (int i=0; i<tree[cur].size(); i++) {
        int tmp = dfs(tree[cur][i]);
        list.push_back(tmp);
    }
    sort(list.begin(), list.end(), compare);


    int res = 0;
    for (int i=0; i<list.size(); i++) {
        res = max(res, list[i] + i+1);
    }

    return res;
}

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

    cin >> N;
    tree.resize(N);

    int par_num;
    cin >> par_num;
    for (int i=1; i<N; i++) {
        cin >> par_num;
        tree[par_num].push_back(i);
    }

    if (N == 1) {
        cout << 0 << "\n";
    }
    else {
        int tmp = dfs(0);
        cout << tmp << "\n";
    }

    return 0;
}

 

dfs 함수 내부에 있는 for 문이 위로 전달하는 그 노드에서 가용되는 최대 시간인데, 내림차순으로 정렬한 후, 가장 큰 수가 앞에 와서 그걸 사용하면 될 것 같지만,

부모노드에서 자식노드를 방문할 때, 한번에 하나의 노드밖에 방문할 수 없기 때문에, 몇번 째 방문인지 + 해당 노드의 자식노드 수를 합쳐줘야 한다.

회고

오랫만에 골드 상위권 문제를 풀이했는데, 오랫만이라 그런지 더 어렵고 생각보다 시간을 더 소요했다.

 

하지만, 이 알고리즘 스터디에 참여했던 이유가 이런 문제들을 많이 풀어보려고 참여했던 것 이어서 나름 괜찮았다.

 

이 문제의 분류가 TreeDP, Greedy, Sort, Tree 였는데, 정말 그 전부를 다 활용할 줄은 몰랐다. 여러 알고리즘이나 자료구조가 이렇게 잘 짜여져있는 문제는 처음이었는데, 풀고 이해하고나니까 재밌었다.

 

요즘 코딩테스트 문제들이 점점 어려워지는 것 같은데, 이런 문제들도 나왔을 때, 당황하지 않으려면 많이 풀어보는 것만이 답인것 같다.