[백준] 10159 저울

문제 출처: https://www.acmicpc.net/problem/10159

10159번: 저울

 

1. 입력

: 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다.

: 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다.

: 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

 

2. 출력

: 여러분은 N개의 줄에 결과를 출력해야 한다.

: i 번째 줄에는 물건 i 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

 

3. 풀이

: 플로이드-와샬 알고리즘을 사용해 풀 수 있다.

: 먼저 입력값들을 A가 B보다 무겁다면 인접행렬의 A행 B열 값을 1로 B행 A열 값을 -1로 표시해 놓는다.

: 플로이드-와샹 알고리즘을 사용해 각각의 값에 접근하면서 만약 경유지를 통했을 때 양쪽 다 1 또는 -1 가지게 된다면

i번째와 k번째를 비교할 수 있다는 뜻이므로 그 값을 i행 k열에 넣어준다.

 

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static int[][] adj;
	public static void main(String[] args) throws Exception{
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		adj = new int[N+1][N+1];
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			adj[v1][v2] = 1;
			adj[v2][v1] = -1;
		}
		
		for(int j = 1; j < N+1; j++) {
			for(int i = 1; i < N+1; i++) {
				if(i == j) continue;
				for(int k = 1; k < N+1; k++) {
					if(k  == i || k==j) continue;
					if(adj[i][j] != 0 && adj[i][j]==adj[j][k])adj[i][k] = adj[i][j];
				}
			}
		}
		int res = 0;
		for(int i = 1; i < N+1; i++) {
			int cnt = 0;
			for(int j = 1; j< N+1; j++) {
				if(i == j) continue;
				if(adj[i][j] == 0) cnt++;
			}
			sb.append(cnt+"\n");
		}
		System.out.println(sb);
	}
}