[BOJ 10159] 저울 (Java)

문제

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

10159번: 저울

 

풀이

플로이드 와샬 알고리즘을 사용하여 풀 수 있다.

ex) 1 > 2 , 2 > 3   ===>  1 > 3

 

소스코드

package floyd;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BOJ10159 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		int map[][] = new int[N+1][N+1];
		
		StringTokenizer st = null;
		for(int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			// a > b
			map[a][b] = 1;
			map[b][a] = -1;
		}
		
		for(int k = 1; k <= N; k++) {
			for(int i = 1; i <= N; i++) {
				for(int j = 1; j <= N; j++) {
					if(map[i][k] == 1 && map[k][j] == 1) {
						map[i][j] = 1;
						map[j][i] = -1;
					}
					if(map[i][k] == -1 && map[k][j] == -1) {
						map[i][j] = -1;
						map[j][i] = 1;
					}
				}
			}
		}
		
		for(int i = 1; i <= N; i++) {
			int cnt = 0;
			for(int j = 1; j <= N; j++) {
				if(i == j) continue;
				if(map[i][j] == 0) cnt++;
			}
			System.out.println(cnt);
		}	
	}
}