백준 9470 Strahler 순서 - 노드마다 count를 세야하는 위상정렬 문제

문제 링크

www.acmicpc.net/problem/9470

9470번: Strahler 순서

풀이 아이디어 (처음 틀린 방식)

오랜만에 푸는 위상정렬 문제였다.

본인은 이 문제를 2번이나 틀리고 3번째만에 맞추게 되었는데, 

2번씩이나 틀린 이유는 이 문제를

노드마다 count를 안 세고 야매로 풀려다가 된통 당했기 때문이다.

 

 

맨처음 틀린 접근 방식은 다음과 같다.

위상정렬로 순서대로 접근하는 건 다른 문제들과 똑같은 방식이니 패스하겠다.

 

처음에 int cost[1001]을 잡고,

해당 노드(x)에 처음으로 n짜리 강이 흘러 들어올 때는 : cost[x]는 0->n으로 업데이트

해당 노드(x)에 cost가 m인데 n짜리 강이 흘러 들어올 때는 (m<n) : cost[x]는 m->n으로 업데이트

해당 노드(x)에 이미 strahler값이 n인데 n짜리 강이 한번더 흘러 들어올 때는 cost[x]는 n->n+1으로 업데이트

 

틀린 방식이었다. 반례를 생각 못했다.

특정 노드에 2,2,3짜리 강이 순서대로 들어온다고 가정했을때 strahler값은 3이 되어야 하나,

위의 방식대로라면 4가 나오게 되었다.

반례

1
1 14 13
1 9
2 9
3 10
4 10
5 11
6 11
7 12
8 12
11 13
12 13
9 14
10 14
13 14

풀이 아이디어(올바른 방식)

애초에 강이 특정 노드로 흘러들어올때, 흘러들어오는  강의 strahler 값과 해당값이 들어온 횟수를 한꺼번에 세고,

값 update는 맨 나중에 진행되었어야 했다. --> 문제에서 요구한 그대로.

따라서 strahler 값을 저장하는 int cost[] 를 pair<int,int> cost[] 로 구조를 바꿔주었다.

 

cost[x] = {i,j}일 때

i짜리 강이 j번 들어온 것이다.

 

만약 k>i짜리 강이 새로 들어오면 값 업데이트는 어떻게 해야 할까?

{i,j} --> {k,1} 로 업데이트 해주면 된다.

 

작은 강이 들어오면 당연히 무시해주면 되고,

같은 값i 의 다른 강이 들어오면 {i,j} --> {i,j+1}로 업데이트해준다.

 

마지막에 numOfParent (흔히 위상정렬에 쓰는 degree) 값이 0이 되면

second 값이 1을 넘기는지 안넘기는지 확인하고 값 마지막으로 업데이트.

해주면 풀 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

int t;
int numOfParent[1001];
vector<int> tree[1001];
pair<int,int> cost[1001];
queue<int> q;

void init(int n){
    fill_n(numOfParent,n+1,0);
    for(int i=0; i<=n; i++){
        cost[i]={0,0};
        tree[i].clear();
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    cin>>t;
    while(t--){
        int ans = 0;
        int k,m,p;
        cin>>k>>m>>p;

        init(m);
        while(!q.empty()) q.pop();
        for(int i=0; i<p; i++){
            int s,t;
            cin>>s>>t;
            tree[s].push_back(t);
            numOfParent[t]++;
        }

        for(int i=1; i<=m; i++){
            if(!numOfParent[i]) {
                cost[i]={1,1};
                q.push(i);
            }
        }

        while(!q.empty()){
            int x= q.front();
            q.pop();
            for(int next: tree[x]){
                numOfParent[next]--;
                if(cost[next].first==0) cost[next]={cost[x].first,1};
                else if(cost[next].first<cost[x].first) cost[next]={cost[x].first,1};
                else if(cost[next].first==cost[x].first) cost[next].second++;
                if(!numOfParent[next]) {
                    if(cost[next].second>1){
                        cost[next]={cost[next].first+1,1};
                    }
                    q.push(next);
                }
            }
        }
        ans = cost[m].first;
        cout<<k<<" "<<ans<<"\n";
    }

}