[BOJ 10159] 저울 (Java)

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

10159번: 저울

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

public class Main_BOJ_10159 {
	static int N, M;
	static int[][] floyd;
	static int INF=987654321;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		M=Integer.parseInt(br.readLine());
		floyd=new int[N+1][N+1];
		for (int i = 0; i < N+1; i++) {
			Arrays.fill(floyd[i], INF);
		}
		for (int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			floyd[a][b]=1;
			floyd[b][a]=-1;
			
		}
		for (int k=1; k<=N; k++) {
			for (int i=1; i<=N; i++) {
				if (i==k) continue;
				for (int j=1; j<=N; j++) {
					if (i==j || k==j) continue;
					if (floyd[i][k]!=INF && floyd[k][j]!=INF) {
						if (floyd[i][k]*floyd[k][j]>0 && floyd[i][j]>floyd[i][k]+floyd[k][j]) {
							floyd[i][j]=floyd[i][k]+floyd[k][j];
						}
					}
				}
			}
		}
		for (int i=1; i<=N; i++) {
			int cnt=0;
			for (int j=1; j<=N; j++) {
				if (i!=j && floyd[i][j]==INF) cnt++;
			}
			//System.out.println();
			System.out.println(cnt);
		}
	}

}

너무 복잡하게 풀었다..

 

다른 분의 코드를 보니(https://jow1025.tistory.com/117)

삼단논법이다: a>b b>c => a>c!

즉 이를 이용해서 (a,b)가 연결되면 floyd[a][b]=1 로 표시해주고,

floyd[a][k], floyd[k][c] => 이 2개가 서로 연결되었는지 체크하고 연결되었으면 floyd[a][c]=1로 해준다.

 

연결성을 체크할때는

a->c, c->a 양쪽을 모두 체크해준다.