[BaekJoon] 9470 Strahler 순서 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    static int K, M, P;
    static HashMap<Integer, ArrayList<Integer>> parentNode;
    static ArrayList<Integer>[] orders;
    static int[] childNodeNum, strahlerOrder;

    static void input() {
        K = scanner.nextInt();
        M = scanner.nextInt();
        P = scanner.nextInt();
        childNodeNum = new int[M + 1];
        strahlerOrder = new int[M + 1];
        orders = new ArrayList[M + 1];
        parentNode = new HashMap<>();
        for(int node = 1; node <= M; node++) {
            parentNode.put(node, new ArrayList<>());
            orders[node] = new ArrayList<>();
        }

        for(int edge = 0; edge < P; edge++) {
            int start = scanner.nextInt(), end = scanner.nextInt();

            childNodeNum[end]++;
            parentNode.get(start).add(end);
        }
    }

    static void solution() {
        getStrahlerOrder();

        int[] sortedOrders = Arrays.stream(strahlerOrder).boxed()
                .sorted(Collections.reverseOrder())
                .mapToInt(Integer :: valueOf)
                .toArray();

        sb.append(K).append(' ').append(sortedOrders[0]).append('\n');
    }

    static void getStrahlerOrder() {
        Queue<Integer> queue = new LinkedList<>();
        for(int node = 1; node <= M; node++) {
            if(childNodeNum[node] == 0) {
                queue.offer(node);
                strahlerOrder[node] = 1;
            }
        }

        while(!queue.isEmpty()) {
            int cur = queue.poll();

            for(int next : parentNode.get(cur)) {
                orders[next].add(strahlerOrder[cur]);
                childNodeNum[next]--;

                if(childNodeNum[next] == 0) {
                    if(orders[next].size() == 1) strahlerOrder[next] = orders[next].get(0);
                    else {
                        Collections.sort(orders[next], Collections.reverseOrder());
                        int max = orders[next].get(0);

                        if(max == orders[next].get(1)) strahlerOrder[next] = max + 1;
                        else strahlerOrder[next] = max;
                    }
                    queue.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }
        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어지는 간선의 정보를 이용하여 아래와 같이 간선의 정보를 저장합니다.
  • 각 노드에서 흘러 만나는 노드들을 parentNode라는 HashMap에 저장하고, 각 노드로 흘러 들어오는 노드들의 개수를 childNodeNum에 저장합니다.
  • 다른 변수들에 대해 설명하자면, strahlerOrder는 각 노드의 Strahler 순서를 나타내고, orders는 각 노드로 흘러 들어오는 노드들의 Strahler 순서를 저장하기 위한 ArrayList 배열입니다.
• 위상 정렬을 이용하여 각 노드의 Strahler 순서를 구합니다.
  • 우선 각 노드들의 childNodeNum 값을 보고 자신으로 흘러 들어오는 노드가 없다면 해당 노드의 Strahler 순서를 1로 설정하고 Queue에 해당 노드들을 넣습니다.
  • Queue가 빌 때까지 queue에서 값을 하나씩 빼며, 현재 뺀 노드를 cur이라고 한다면, 각 cur에 대해서 아래 작업을 진행하며 각 노드의 Strahler 순서를 구합니다.
    • cur에서 흘러 만나는 노드들을 순회하며 만나는 노드들을 각각 next라고 한다면, next의 orders에 cur의 Strahler 순서를 넣습니다.
    • 그리고 cur은 next와 비교하여 정렬이 완료되었기 때문에 next의 childNodeNum의 값을 1 뺍니다.
    • 만약 next의 childeNodeNum 값이 0이 되었다면, next의 Strahler 순서를 결정합니다.
      • 만약 next의 order에 데이터가 하나 밖에 없다면, next로 흘러 들어오는 노드가 한 개라는 뜻이기 때문에 가장 큰 강의 순서가 order에 들어있는 데이터이므로 해당 값을 Strahler 순서로 정합니다.
      • 그렇지 않다면, orders를 내림차순으로 정렬합니다. 이 때, 가장 큰 값인 0번 index의 값과 1번 index 값을 비교하여 두 값이 같다면, 가장 큰 강의 순서가 2개 이상이라는 뜻이므로 next의 Strahler 순서를 {order의 0번 index의 값 + 1}로 설정하고 그렇지 않다면 가장 큰 강의 순서가 1개이기 때문에 해당 값을 next의 Strahler 순서로 설정합니다.
    • 그리고 queue에 next를 넣어 이후 정렬에 사용합니다.
• 이제 모든 노드의 Strahler 순서가 strahlerOrder에 담겨있으니 이를 내림차순으로 정렬하여 0번째 index 값이 주어진 하천계의 Strahler 순서값이 됩니다.