[JAVA] 백준 2458 키 순서

문제

입력

출력

풀이: 플로이드 와샬

NXN이차원 배열을 0으로 초기화하고, 초기 입력값을 토대로 a학생의 키가 b학생의 키보다 클 경우 array[a][b] = 1, array[b][a] = -1로 초기화 한다.
이후 플로이드 와샬 알고리즘을 적용한다.

1. array[a][k] == x, array[k][b] == x 일때, array[a][b] = x로 업데이트한다.
2. 최종 배열의 행마다 0이 존재하는지 확인한다.(본인 행 제외)
3. 0이 없는 행의 개수를 출력한다.

코드

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class p5643키순서 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testcase = Integer.parseInt(br.readLine());
		for(int t=1; t<= testcase; t++) {
			int N = Integer.parseInt(br.readLine());
			int M = Integer.parseInt(br.readLine());
			int[][] table = new int[N][N];
			for(int i=0; i<M; i++) {
				st= new StringTokenizer(br.readLine());
				int big = Integer.parseInt(st.nextToken())-1;
				int small = Integer.parseInt(st.nextToken())-1;
				table[big][small] = 1;
				table[small][big] = -1;
			}
			for(int k=0; k<N; k++) {
				for(int i=0; i<N; i++) {
					for(int j=0; j<N; j++) {
						if(table[i][k]==1&&table[k][j]==1) {
							table[i][j] = 1;
						} else if(table[i][k] ==-1&&table[k][j]==-1) {
							table[i][j] = -1;
						}
					}
				}
			}
			int ans  =0;
			for(int i=0; i<N; i++) {
				int count = 0;
				for(int j=0; j<N; j++) {
					if(table[i][j]!=0)
						count++;
				}
				if(count==N-1)
					ans++;
			}
			System.out.println("#"+t+" "+ans);
		}
	}
}