[알고리즘][X] 키 순서

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo

SW Expert Academy

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	
	static int N;
	static int M;
	static boolean[][] battle;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= T; testCase++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			
			battle = new boolean[N+1][N+1];
			for (int i = 1; i<=N; i++) {
				for (int j = 1; j <=N; j++) {
					if (i==j) {
						battle[i][j] = true;
					}
				}
			}
			int[] indegree = new int[N+1];
			boolean[] visited = new boolean[N+1];
			List<Integer>[] graph = new List[N+1];
			for (int i = 1; i <= N; i++) {
				graph[i] = new ArrayList<>();
			}
			
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				graph[a].add(b);
				indegree[b]++;
			}
			
			Queue<Integer> queue = new ArrayDeque<>();
			for (int i = 1; i <= N; i++) {
				if (indegree[i] == 0) {
					queue.add(i);
				}
			}
			
			while (!queue.isEmpty()) {
				int cur = queue.poll();
				visited[cur] = true;
				for (int next : graph[cur]) {
					for (int i = 1; i <= N; i++) {
						if (!visited[i]) {
							continue;
						}
						if (battle[cur][i] == true) {
							battle[next][i] = true;
							battle[i][next] = true;
						}
					}
				}
				for (int next : graph[cur]) {
					battle[cur][next] = true;
					battle[next][cur] = true;
					indegree[next]--;
					if (indegree[next] == 0) {
						queue.add(next);
					}
				}
			}
			
//			print();
			int res = 0;
			for (int i = 1; i <= N; i++) {
				int count = 0;
				for (int j = 1; j <= N; j++) {
					if (battle[i][j]) {
						count++;
					}
				}
				if (count == N) {
					res++;
				}
			}
			sb.append("#").append(testCase).append(" ").append(res).append("\n");
			
		}
		System.out.println(sb);
	}
	
	private static void print() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(battle[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}

위상 정렬을 이용한 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution2 {
	
	static int N;
	static int M;
	static int[][] battle;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= T; testCase++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			
			battle = new int[N+1][N+1];
			for (int i = 1; i<=N; i++) {
				for (int j = 1; j <=N; j++) {
					if (i==j) {
						battle[i][j] = 1;
					}
				}
			}

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				battle[a][b] = 1;
				battle[b][a] = -1;
			}
//			print();
			
			for (int k = 1; k <= N; k++) {
				for (int i = 1; i <= N; i++) {
					for (int j = 1; j <= N; j++) {
						if (battle[i][k] == battle[k][j] && battle[i][k] != 0) {
							battle[i][j] = battle[i][k];
						}
					}
				}
			}
			
			
//			print();
			int res = 0;
			for (int i = 1; i <= N; i++) {
				int count = 0;
				for (int j = 1; j <= N; j++) {
					if (battle[i][j] != 0) {
						count++;
					}
				}
				if (count == N) {
					res++;
				}
			}
//			print();
			sb.append("#").append(testCase).append(" ").append(res).append("\n");
			
		}
		System.out.println(sb);
	}
	
	private static void print() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(battle[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}

플로이드워셜을 이용한 풀이

- 서로 0으로 같을 수 있는 순간을 주의한다