[C/C++] 백준 - 9470번 : Strahler 순서 (위상정렬)

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

9470번: Strahler 순서

문제

지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳, 바다와 만나는 곳이다.

네모 안의 숫자는 순서를 나타내고, 동그라미 안의 숫자는 노드 번호를 나타낸다.

하천계의 Strahler 순서는 다음과 같이 구할 수 있다.

• 강의 근원인 노드의 순서는 1이다.
• 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.

하천계의 순서는 바다와 만나는 노드의 순서와 같다. 바다와 만나는 노드는 항상 1개이며, 위의 그림의 Strahler 순서는 3이다.

하천계의 정보가 주어졌을 때, Strahler 순서를 구하는 프로그램을 작성하시오.

실제 강 중에서 Strahler 순서가 가장 큰 강은 아마존 강(12)이며, 미국에서 가장 큰 값을 갖는 강은 미시시피 강(10)이다.

노드 M은 항상 바다와 만나는 노드이다.

입력

첫째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1000)가 주어진다.

각 테스트 케이스의 첫째 줄에는 K, M, P가 주어진다. K는 테스트 케이스 번호, M은 노드의 수, P는 간선의 수이다. (2 ≤ M ≤ 1000) 다음 P개 줄에는 간선의 정보를 나타내는 A, B가 주어지며, A에서 B로 물이 흐른다는 뜻이다. (1 ≤ A, B ≤ M) M은 항상 바다와 만나는 노드이며, 밖으로 향하는 간선은 존재하지 않는다.

출력

각 테스트 케이스마다 테스트 케이스 번호와 입력으로 주어진 하천계의 Strahler 순서를 한 줄에 하나씩 출력한다.

---

이 문제를 읽어보면 알아내야 하는 최종 결과가 밖으로 향하는 간선이 존재하지 않는 M번 노드의 Strahler 순서이다.

이 정보를 알기 위해서는 해당 노드로 들어오는 노드의 Strahler 순서 정보를 알아야만 한다. 다른 노드들도 마찬가지이다. 현 노드의 Strahler의 정보를 알기 위해서는 해당 노드로 들어오는 모든 노드의 Strahler 순서 정보를 알고 있어야한다.

 

즉, 진입차수가 존재하지 않는 노드부터 시작하여 Strahler 순서를 저장하고, 그 정보를 바탕으로 진입차수가 큰 노드의 정보까지 최신화하여 알아가야하는 "위상정렬" 문제이다.

 

Step 1.

문제에 주어진 예시처럼 진입차수가 존재하지 않는 노드부터 시작한다.

진입차수가 존재하지 않는 노드들의 Strahler 순서는 무조건 1이다.

 

Step 2.

Step 1. 에서 저장한 노드를 시작 노드로 연결되어있는 다른 노드들의 값을 위상정렬을 통해 최신화해나간다. 문제에 주어진 조건대로 처리를 하면 된다.

이 때 주의해야 할 점이 어떤 한 노드가 존재한다고 가정하자 (Node로 칭함). 그리고 이 Node로 들어오는 강이 5개 있다고 가정해보자. 그리고 그 5개 강의 Strahler 순서가 4 5 5 6 7 이라고 생각해보자.

 

그럼 문제에 주어진 조건대로 Node의 Strahler 순서를 알아보면 어떤 값이 되어야할까? 가장 큰 Strahler 순서값이 7이 되어야한다.

눈으로 직관적으로 확인한다면 바로 알 수 있겠지만 코드로 이를 구현하면 값 하나 하나 대조해서 저장해야하기 때문에 놓치기 쉬운 부분이 존재한다.

 

바로 이러한 부분이다.

Node의 값은 아직 0이고 4랑 비교하면 4가 최대값이기 떄문에 4를 저장한다.

Node의 값은 4이고 다음 값인 5와 비교하였을 때 최대값이 5이기 때문에 5를 저장한다.

Node의 값이 5이고 다음 값도 동일한 5이기 때문에 위 조건에 따라 6으로 값이 커진다.

Node의 값이 6이고 다음 값 또한 6이다. 따로 처리를 해주지 않으면 같은 값이 온 것이기 때문에 7로 된다.

Node의 값이 7이고 다음 값 또한 7이다. 따로 처리를 해주지 않으면 같은 값이 온 것이기 때문에 8로 된다.

 

이렇게 주어진 조건을 코드로 구현하면 위 부분을 놓치기 쉽다. 이 부분만 잘 처리해준다면 이 문제는 위상정렬대로 쉽게 해결할 수 있다.

나는 방문처리와 업데이트 여부를 관리해주는 bool 배열을 통해 처리해주었다.

 

1. 아직 방문하지 않은 노드는 방문 처리를 해주고 들어오는 강의 순서를 현 노드의 순서값으로 저장해준다.

2. 만약 방문했던 노드로 들어오는 강이 존재한다면?

    2-1. 최대값과 동일하고 아직 업데이트 한 적이 없다면 업데이트 여부를 true로 바꿔주고 순서값을 현 값 + 1로 해준다.

    2-2. 저장되어있는 값보다 전 노드의 순서값이 더 크다면 현 노드의 값을 더 큰 전 노드의 순서값으로 바꾸고 업데이트 여부가 true였어도 false로 변환해준다. 이유는 최대값으로 갱신되었기 때문

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 987654321
#define endl '\n'

using namespace std;

int K, M, P;
vector<int> adj[1000 + 1];
int in[1000 + 1], level[1000 + 1];
bool visited[1000 + 1], update[1000 + 1];

void topologySort(queue<int> &q){
    while(!q.empty()){
        int cur = q.front();
        q.pop();

        for(auto &next : adj[cur]){
            if(!visited[next]){
                visited[next] = true;
                level[next] = level[cur];
            }
            else{
                if(level[next] == level[cur] && !update[next]) {
                    update[next] = true;
                    level[next] = level[cur] + 1;
                }
                else{
                    if(level[next] < level[cur]){
                        update[next] = false;
                        level[next] = level[cur];
                    }
                }
            }

            --in[next];
            if(!in[next]){
                q.push(next);
            }
        }
    }
}

pair<int, int> solution(int turn, int pos){
    queue<int> q;
    for(int i=1;i<=M;i++){
        if(!in[i]){
            q.push(i);
            level[i] = 1;
            visited[i] = true;
        }
    }
    topologySort(q);

    return {turn, level[pos]};
}

void clear(int node){
    memset(in, 0, sizeof(in));
    memset(visited, false, sizeof(visited));
    memset(update, false, sizeof(update));
    for(int i=0;i<node;i++){
        adj[i].clear();
    }
}

void input(){
    int testCase;
    cin >> testCase;

    while(testCase--){
        cin >> K >> M >> P;
        for(int i=0;i<P;i++){
            int from, to;
            cin >> from >> to;
            adj[from].push_back(to);
            in[to]++;
        }

        pair<int, int> answer = solution(K, M);
        cout << answer.first << " " << answer.second << endl;
        
        clear(M);
    }
}

int main(){
    fastio;
    input();

    return 0;
}