문제 이해

Strahler 순서는 아래와 같이 구할 수 있다.

1. 강의 근원 노드(Input이 없는 Node)의 순서는 1이다.

2. 인접한 Node 중 Input값을 늘리는 (A ⇒ B에서 A Node) 순서 중 최대값을 i라고 하자. 만약 i인 강이 1개이면 i, 2개 이상이면 i+1의 순서를 가진다.

이렇게 구한 순서 중 최댓값을 Strahler 순서라고 말할 수 있다.
그래프가 주어질 때, Case와 그 때의 Strahler순서를 출력하는 문제이다

---

문제 출력

그래프를 보면 알겠지만, 노골적으로 이 그래프가 DAG임을 알리고 있다.
따라서, DAG에 가장 효과적인 위상정렬을 고려해보았다.

알고리즘 순서는 아래와 같다.

1. Input값이 0인 Node들을 찾는다.

2. 이 Node들을 지우는 동시에, 화살표가 가리키는 방향에 존재하는 Node(A ⇒ B에서 B Node)의 list 공간에 해당 Node의 Strahler 순서를 저장한다.

3. 만일 Input이 0이 되는 Node가 존재한다면 Queue에 저장한다.

Strahler 순서를 저장하는 방법은 아래와 같다.

1. A ⇒ B에서 A를 지울 때, A의 Strahler 순서 값을 list[B]에 저장한다.

2. B가 Queue에서 poll되었을 경우, 먼저 list[B]를 내림차순으로 정렬한다.

3. list[B]의 size가 0 : 존재하지 않는다. input이 처음부터 0인 Node들도 초기 Strahler 값인 1을 저장시켜줄 것이므로 무조건 1 이상이다.

   list[B]의 size가 1 : B로 들어오는 강이 하나밖에 없으므로, list[B]에 저장된 유일한 값을 B의 Strahler 순서로 저장한다.

   list[B]의 size가 2 이상 : 먼저 내림차순으로 정렬한다.

   (1) list[B].get(0) = list.get(1) : 노드로 들어오는 강의 순서 중 가장 큰 값이 2개 존재하는 것이므로, list[B].get(0) + 1을 Starhler 순서로 지정한다.

   (2) list[B].get(0) != list.get(1) : 노드로 들어오는 강의 순서 중 가장 큰 값은 list[B].get(0) 하나밖에 존재하지 않으므로, list[B].get(0)을 Strahler 순서로 지정한다.

---

코드

import java.io.*;
import java.util.*;

class Node implements Comparable<Node>{
	int num;
	int size;
	
	public Node(int num, int size) {
		this.num = num;
		this.size = size;
	}
	
	@Override
	public int compareTo(Node n) {
		return this.num - n.num;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int K;
	static int N,E;
	static ArrayList<Integer>[] list;
	static int[] ans;
	static int[] input;
	
	static void sort() {
		Queue<Integer> queue = new LinkedList<>();
		ArrayList<Integer>[] node = new ArrayList[N+1];
		
		for(int i =1;i<N+1;i++) {
			node[i] = new ArrayList<>();
			if(input[i]==0) {
				queue.add(i);
				ans[i] = 1;
				node[i].add(1);
			}
		}
		
		while(!queue.isEmpty()) {
			int t = queue.poll();
			
			Collections.sort(node[t], Comparator.reverseOrder());
            // node[t]를 내림차순으로 정렬
            // node[t] : A -> t로 이어진 모든 A의 Strahler순서가 저장된 
            //           ArrayList
				
			if(node[t].size()<=1) { 
            // size = 1인 상황이다. 저장된 유일한 값이 t의 Strahler 값이다.
				ans[t] = node[t].get(0);
			}
			else if(node[t].get(0)==node[t].get(1)) {
                // 역순으로 배열되었으므로, get(0) = get(1)이라는 것은
                // get(0)과 get(1)이 최대 Strahler 값이라는 의미이다. 
                // 최대값이 2개 존재하므로 정의에 의해 
                // get(0) + 1이 Strahaler 값이 될 것이다.
				ans[t] = node[t].get(0)+1;
			}
			else {
                // 이러면 node[t].size<=1과 똑같은 상황이니 굳이 if문을 하나 
                // 추가해야하나 싶을 수도 있다
                // 하지만, if문을 삭제하면 get(1)을 접근할 때 
                // ArrayIndexOutOfBoundsException이 발생한다.
				ans[t] = node[t].get(0);
			}
			
			for(int s:list[t]) {
				node[s].add(ans[t]); 
                // t -> s인 상황에서 node[s]에 t의 Strahler값을 저장 시킴
				input[s]--;
				if(input[s]==0) queue.add(s);
			}
		}

		int max = Integer.MIN_VALUE;
		for(int i =1;i<N+1;i++) {
			max = Math.max(ans[i],max); 
            // Strahler 중 최댓값을 찾아야 함
		}
		sb.append(K+" "+max+"\n");
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		
		for(int t=0;t<T;t++) {
		
			K = sc.nextInt();
			N = sc.nextInt(); //Node 개수
			E = sc.nextInt(); //Edge 개수
		
			list = new ArrayList[N+1];
			input = new int[N+1];
			ans = new int[N+1];
			
			for(int i =1;i<N+1;i++) list[i] = new ArrayList<>();
			
			for(int i =0;i<E;i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				
				list[start].add(end);
				input[end]++;
			}
			
			sort();
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2,3번째 줄 틀렸습니다 : list[B] 공간을 만들기 싫어서 다른 방법을 사용해봤다. 그런데, Node 하나당 int형 2개의 공간이 필요했고, 심지어 매번 숫자를 넣을 때마다 해당 숫자가 최댓값인지 아닌지 판단하는 알고리즘까지 입력되었어야 했다. 이런 부분을 모두 구현하려 하다보니 실수가 나와 틀렸다.