[BOJ_10159] 저울

설명

---

특이한 알고리즘 기법이 사용된 문제는 아니고 일반적인 플로이드 와셜 문제인데요. 다만, 수의 비교를 통해서 갈 수 있는 곳을 찾아내는 문제다 보니 나 보다 큰 수는 어디까지 탐색 할 수 있는지 파악 할 수 있는 곳을 찾고 나 보다 작은 수는 어디까지 탐색 할 수 있는 지 탐색이 필요합니다. 따라서, 아래와 같이 코드 구현을 하였습니다.

코드

---

 

 

package BOJ.shortest_path;

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

public class BOJ_10159 {
    static int N,M;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        N = Integer.parseInt(tk.nextToken());
        tk = new StringTokenizer(in.readLine()," ");
        M = Integer.parseInt(tk.nextToken());
        int map[][] = new int[N][N];
        int reverseMap[][] = new int[N][N];
        for(int tmp[] : map) {
            Arrays.fill(tmp, 1000_000_000);
        }
        for(int tmp[] : reverseMap) {
            Arrays.fill(tmp, 1000_000_000);
        }

        for (int i = 0; i < M; i++){
            tk = new StringTokenizer(in.readLine()," ");
            int from = Integer.parseInt(tk.nextToken()) - 1;
            int to = Integer.parseInt(tk.nextToken()) - 1;
            reverseMap[to][from] = 0;
            map[from][to] = 0;
        }
        for (int k = 0; k < N; k++){
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    if(i == j || (map[i][j] == 0 && reverseMap[i][j] == 0)){
                        continue;
                    }
                    if(map[i][k] + map[k][j] < map[i][j]){
                        map[i][j] = map[i][k] + map[k][j];
                    }
                    if(reverseMap[i][k] + reverseMap[k][j] < reverseMap[i][j]){
                        reverseMap[i][j] = reverseMap[i][k] + reverseMap[k][j];
                    }
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < N; i++){
            cnt = 0;
            for (int j = 0; j < N; j++) {
                if ((reverseMap[i][j] > 0 && map[i][j] > 0) && i != j){
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}

 

10159번: 저울 (acmicpc.net)

10159번: 저울