[백준] 10159 저울

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

10159번: 저울

2021-08-31

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M;
    static int[][] dist;
 
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine().trim());
        M = Integer.parseInt(st.nextToken());
 
        dist = new int[N][N];
 
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i == j) continue;
                dist[i][j] = 987654321;
            }
        }
 
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            dist[a][b] = 1;
        }
 
        for(int mid = 0; mid < N; mid++) {
            for(int start = 0; start < N; start++) {
                for(int end = 0; end < N; end++) {
                    if(dist[start][end] > dist[start][mid] + dist[mid][end]) {
                        dist[start][end] = dist[start][mid] + dist[mid][end];
                    }
                }
            }
        }
 
        int[] ans = new int[N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i == j) continue;
                if(dist[i][j] == 987654321 && dist[j][i] == 987654321) ans[i]++;
            }
        }
 
        for(int i = 0; i < N; i++) {
            System.out.println(ans[i]);
        }
    }
}

#문제풀이

https://void2017.tistory.com/317?category=820802 

[프로그래머스] 순위

 

어제 푼 이 문제 때문에 풀었다. 완전 똑같은 문제더라..