[BOJ/C++] 1135 - 뉴스 전하기

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

 

---

 

 

 

일단, 가장 처음 떠올린 풀이는 "자식노드 중에서 자식이 가장 많은 노드를 먼저 선택하면 되는거 아닌가?" 라고 생각했다. 따라서 임의의 노드에 대해서, 그 노드를 루트로하는 트리의 노드 수를 탑다운 방식으로 찾아내고, 적절히 정렬해서 풀면 될 것이라고 생각했다. 이때 제출한 코드는 아래와 같다.

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

vector<int> adj[51];
int cnt[51];
int ans;
int count(int idx){
    if(adj[idx].empty()) return cnt[idx]=1;
    for(int x: adj[idx]) cnt[idx] += count(x);
    return ++cnt[idx];
}
void func(int idx, int time){
    if(adj[idx].empty()) return;

    vector<pii> tmp;
    for(int x: adj[idx]){
        tmp.push_back({cnt[x],x});
    }
    sort(all(tmp),greater<>());

    for(auto nxt: tmp){
        func(nxt.Y, ++time);
        ans = max(ans,time);
    }

}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    rep(i,0,n){
        int x; cin>>x;
        if(x==-1) continue;
        adj[x].push_back(i);
    }
    count(0);
    func(0,0);
    cout<<ans<<'\n';

}

 

count 함수에서 서브트리의 노드 수를 계산해주었고, func함수에서 인덱스 번호와 그 인덱스가 활성화 된 시간?을 전달하고, 답이 되는 값은 활성화 된 시간(time)의 최댓값이 된다.

 

당연히 정답일 줄 알고 제출했지만.. 5%에서 틀렸습니다! 를 받는다.

곰곰히 생각해보면 자식노드의 수가 우선순위를 결정하지 않는다는 것을 알 수 있다.

아래의 예시를 보자

1번 노드를 루트로 하는 서브트리의 정점 수는 5, 

2번 노드를 루트로 하는 서브트리의 정점 수 또한 5이다.

서브트리의 정점 수는 같지만, 1번을 먼저 선택하는 경우 소요시간은 5, 2번을 먼저 선택하는 경우 소요시간은 6이다.

따라서 자식노드의 수가 우선순위를 결정할 수 없다.

 

그럼 우선순위를 어떻게 결정할까?

자식노드 수가 아닌, 서브트리에서 전화를 다 돌리는데 걸리는 시간을 우선순위로 매긴다.

사실 당연한건데.. 이걸 생각 못해서 쓸데없이 삽질한 것 같다..

정답코드는 아래와 같다.

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

vector<int> adj[51];
int ans;
int func(int idx){ //idx의 총 통화 시간
    if(adj[idx].empty()) return 0;

    vector<int> tmp;
    for(int x: adj[idx]){
        tmp.push_back(func(x));
    }
    sort(all(tmp),greater<>());

    int ret = 0;
    rep(i,0,tmp.size()){
        ret = max(ret, tmp[i]+i+1);
    }
    return ret;

}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    rep(i,0,n){
        int x; cin>>x;
        if(x==-1) continue;
        adj[x].push_back(i);
    }
    cout<<func(0)<<'\n';

}

 

func 함수는 idx 노드를 루트로 하는 서브트리에서 전화하는데 걸리는 총 시간을 리턴한다.