백준 9470 (Strahler 순서) - java

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은 항상 바다와 만나는 노드이다.

 

유형 : 위상정렬

 

접근 방식

• 평범한 위상정렬 문제이다.
  • 들어오는 간선이 없는 정점을 시작점으로 시작한다.
  • result[i][2]
    • result[i][0] : i 번째 정점의 값
    • result[i][1] : 해당 값의 개수 (후 처리를 위해 저장 필요)
  • 들어오는 간선을 한개 씩 제거하면서 값을 갱신해준다.
    • 개수도 기록해준다.
  • 해당 정점에 들어오는 간선이 전부 제거된 경우 값이 2개 이상 들어온 경우 값을 1증가한다.
• 최댓값이 정답이다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int t = 0;
    static int n = 0;
    static int m = 0;

    static int[] pathNum;
    static int num = 0;

    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        t = Integer.parseInt(st.nextToken());

        for(int k=1;k<=t;k++){
            st = new StringTokenizer(bf.readLine(), " ");
            num = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            pathNum = new int[n+1];

            graph = new ArrayList[n+1];

            for(int i=1;i<=n;i++){
                graph[i] = new ArrayList<>();
            }

            for(int i=1;i<=m;i++){
                st = new StringTokenizer(bf.readLine(), " ");
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                graph[v1].add(v2);

                pathNum[v2] += 1;
            }

            Queue<Node> q = new LinkedList<>();
            int[][] result = new int[n+1][2];
            // result[i][0] -> 값 , result[i][1] -> 개수

            for(int i=1;i<=n;i++){
                if(pathNum[i] == 0){
                    q.add(new Node(i,1)); // 들어오는 간선이 없는 정점 추가
                    result[i][0] = 1; // 1로 초깃값 설정
                    result[i][1] = 0;
                }
            }

            int answer = 0;

            while(!q.isEmpty()){
                Node cur = q.poll();

                for(int next : graph[cur.v]){

                    pathNum[next] -= 1;

                    if(result[next][0] < result[cur.v][0]){
                        result[next][0] = result[cur.v][0];
                        result[next][1] = 1; // 갱신
                    }else if(result[cur.v][0] == result[next][0]){
                        result[next][1] += 1; // 동일한 값일 경우 개수 1개 증가
                    }

                    if(pathNum[next] == 0){

                        int reNum = result[next][0];

                        if(result[next][1] > 1){
                            reNum += 1; // 개수가 2개 이상일 경우 값이 1 증가한다
                        }

                        result[next][0] = reNum;
                        q.add(new Node(next,result[next][0]));
                        answer = Math.max(answer,result[next][0]); // 최댓값
                    }
                }
            }

            sb.append(num+" "+answer+"\n");

        }

        System.out.print(sb);

        bf.close();
    }
}
class Node{
    int v;
    int c;

    Node(int v,int c){
        this.v = v;
        this.c = c;
    }
}