백준 9470번 : Strahler 순서 (Java)

 문제

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

9470번: Strahler 순서

9470 Strahler 순서

 

 구현 방법

Strahler순서를 구하려면 들어오는 강들을 모두 거친 후 들어와야 하기 때문에 위상 정렬 알고리즘을 사용했습니다.

 

Strahler는 하천 순서로 항상 바다와 만나는 노드인 M의 Strahler 순서를 출력해주면 됩니다.

강을 들어갈 때마다 순서와 개수를 저장해야 하기 때문에

1. 노드 번호(강 번호)를 저장할 변수

2. 강의 순서 중 가장 큰 값을 저장할 변수

3. 가장 큰 값의 개수를 저장할 변수

로 Node라는 클래스를 만들었습니다.

 

큐를 돌리면서

1. 내가 이동할 강의 최댓값과 나의 순서를 비교

2. 나의 순서가 크다면 이동할 강의 최댓값과 개수를 변경

3. 같다면 개수를 늘림

4. 만약 내가 이동할 강의 진입 차수가 0이 된다면

4-1. 개수를 체크해 2개 이상이라면 순서 ++

5. 큐에 삽입 후 큐가 빈 값이 되거나 바다와 만나는 M 노드를 만날 때까지 반복

이러한 순서로 구현했습니다!

 

 구현 코드

package BOJ.Gold;

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

public class B9470_Strahler순서 {	
	static int TC, K, M, P, inDegree[];
	static Node nodeArr[];
	static List<List<Integer>> list;
	static Queue<int[]> queue = new LinkedList<>();
	static class Node {
		int num, MAX, cnt;

		public Node(int num, int MAX, int cnt) {
			super();
			this.num = num;
			this.MAX = MAX;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int TC = Integer.parseInt(br.readLine());
		while (TC-->0) {
			st = new StringTokenizer(br.readLine());
			K = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			P = Integer.parseInt(st.nextToken());
			inDegree = new int[M+1];
			nodeArr = new Node[M+1];
			list = new ArrayList<>();
			queue.clear();
			for (int i=0;i<=M;i++) {
				list.add(new ArrayList<>());
				nodeArr[i] = new Node(i, 0, 0);
			}
			for (int i=0;i<P;i++) {
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());
				list.get(v1).add(v2);
				inDegree[v2]++; // 진입 차수 저장
			}
			topology();
			sb.append(K+" "+nodeArr[M].MAX+"\n");
		}
		System.out.println(sb);
	}
	
	static void topology() {
		for (int i=1;i<=M;i++) {
	        	// 강의 근원인 노드의 순서는 1
			if (inDegree[i] == 0) queue.offer(new int[] {i, 1}); 
		}
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			if (now[0] == M) return; // 바다와 만나면 끝
			for (int next : list.get(now[0])) {
            			// 나갈 강이 가진 Strahler의 순서보다 현재의 Strahler의 순서가 크면
				if (nodeArr[next].MAX < now[1]) { 
					nodeArr[next].MAX = now[1]; // Strahler 순서 바꿔주고
					nodeArr[next].cnt = 1; // 개수는 1개
				} else if (nodeArr[next].MAX == now[1]) nodeArr[next].cnt++;
				
				
				if (--inDegree[next] == 0) { // 진입 차수가 0 == 들어갈 수 있는 강이면
	                		// Strahler 순서가 가장 큰 값이 2개 이상이면 큰 값 + 1
					if (nodeArr[next].cnt > 1) nodeArr[next].MAX++; 
                    			// 들어갈 강의 번호와 순서 삽입
					queue.offer(new int[] {next, nodeArr[next].MAX}); 
				}
			}
		}
	}
}

 

정답!