boj 10159 저울

문제 링크

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

문제 풀이

플로이드 워셜 문제

인접 행렬을 구현한다

• a>b 일 때는 map[a][b]=1;
• a<b 일 때는 map[b][a]=2;

입력된 인접행렬을 가지고 플로이드-워셜 알고리즘을 통해 비교

• a>b은 map[a][b]=1이고
• b>c은 map[b][c]=1이므로
• map[a][c]=1

반대로도 마찬기지

• a<b은 map[b][a]=2이고
• b<c은 map[c][b]=2이므로
• map[c][a]=2

map[i][j] > arr[i][k]+arr[k][j] 이용

package BOJ;

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

public class 저울 {

    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[][] map = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b]=1;
            map[b][a]=2;
        }
        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;
                    } else if (map[i][k] == 2 && map[k][j] == 2) {
                        map[i][j]=2;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            int cnt =0;
            for (int j = 1; j <= n; j++) {
                if (i != j && map[i][j] == 0) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}