[PS] BOJ10159 저울 ( Floyd-warshall ) with JAVA

 

10159번: 저울

 

◎ 문제풀이

 

( 1의 무게 ) > ( 4의 무게 ) 이고

( 4의 무게 ) > ( 3의 무게 ) 이면

( 1의 무게 ) > ( 4의 무게 )  > ( 3의 무게 ) 가  성립된다. 

 

위 관계가 성립되지 않는 것의 개수를 구해야 한다. 

 

1,2,3,4 .. 를 노드로 보고

크고 작음의 관계를 간선으로 한다면

그래프를 떠올릴 수 있다. 

 

[Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

 

그래프에서 하나의 노드를 중간노드로 하여 서로 연결되어 있는지 여부를 알아내는 알고리즘에는 플로이드-워셜 알고리즘이 있다. 

 

( 1의 무게 )  > ( 4의 무게 ) 이고

( 4의 무게 )  > ( 3의 무게 ) 이면

( 1의 무게 )  > ( 4의 무게 )  > ( 3의 무게 ) 가  성립된다. 

 

성립된다면 동시에

 

( 4의 무게 ) < ( 1의 무게 ) 이고

( 3의 무게 ) < ( 4의 무게 ) 이면

( 3의 무게 ) < ( 4의 무게 )  < ( 1의 무게 ) 도  성립된다. 

 

인간이 보기에는 같은 말이지만

알고리즘 관점에서는 다른 말이다. 

 

플로이드-워셜 알고리즘에서는 양방향 관계를 모두 정의해주어야 한다. 

 

1의 무게가 4의 무게보다 크다는 것은 1의 관점이다.

4의 관점에서는 4의 무게는 1의 무게보다 작다. 

 

큰 경우 : 1

작은 경우 : -1 

무게관계를 모르는 경우 : 0 

 

0의 개수를 구해주면 답을 알 수 있다. 

 

 

◎ 코드

package org.example.shortestpath;

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

//BOJ10159 저울
public class Floyd3 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] floyd = new int[n + 1][n + 1];

        // floyd 자료구조 초기화 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(i==j) floyd[i][j] = 1;
            }
        }

        StringTokenizer st;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            // 양방향 관계
            floyd[num1][num2] = 1;  // num1 > num2 (num1이 크다)
            floyd[num2][num1] = -1; // num2 < num1 (num2가 작다)

        }

        for (int mid = 1; mid <= n; mid++) {
            for (int start = 1; start <= n; start++) {
                for (int end = 1; end <= n; end++) {
                    
                    // start > mid 이고 mid > end 인 경우 
                    if (floyd[start][mid] == 1 && floyd[mid][end] == 1) {
                        floyd[start][end] = 1;
                    }

                    // start < mid 이고 mid < end 인 경우
                    if (floyd[start][mid] == -1 && floyd[mid][end] == -1) {
                        floyd[start][end] = -1;
                    }
                }
            }
        }

        // 출력
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= n; j++) {
                // 관계가 성립되지 않은 경우만 카운트
                if (floyd[i][j] == 0) count++; 
            }
            System.out.println(count);
        }

    }


}