[BaekJoon] 10159 저울 (Java)

1.  문제 링크

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

2.  문제

요약

• 무게가 서로 다른 N개의 물건이 있고, 각 물건은 1부터 N까지 번호가 매겨져 있습니다.
• 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지 측정한 결과표를 가지고 있고, 이 결과표를 통해 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있습니다.
• 비교 결과가 모순되는 입력은 없다고 가정합니다.
• 물건의 개수 N과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 5보다 크거나 같고 100보다 작거나 같은 물건의 개수 N이 주어지고 두 번째 줄에 0보다 크거나 같고 2,000보다 작거나 같은 미리 측정된 물건 쌍의 개수 M이 주어집니다. 세 번째 줄부터 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어집니다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁습니다.
• 출력: N개의 줄에 결과를 출력합니다. i번째 줄에는 물건 i와 비교 결과를 알 수 없는 물건의 개수를 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M;
    static HashMap<Integer, ArrayList<Integer>> map;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new HashMap<>();
        for(int stuff = 1; stuff <= N; stuff++) map.put(stuff, new ArrayList<>());
        for(int comparison = 0; comparison < M; comparison++) {
            int heavy = scanner.nextInt(), light = scanner.nextInt();
            map.get(light).add(heavy);
        }
    }

    static void solution() {
        int[][] distances = new int[N + 1][N + 1];
        for(int stuff = 1; stuff <= N; stuff++) {
            Arrays.fill(distances[stuff], Integer.MAX_VALUE);
            dijkstra(stuff, distances[stuff]);
        }
        int[] nonComparable = new int[N + 1];
        for(int stuff1 = 1; stuff1 <= N; stuff1++) {
            for(int stuff2 = 1; stuff2 <= N; stuff2++) {
                if(stuff1 == stuff2) continue;
                if(distances[stuff1][stuff2] == Integer.MAX_VALUE && distances[stuff2][stuff1] == Integer.MAX_VALUE)
                    nonComparable[stuff1]++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int stuff = 1; stuff <= N; stuff++) sb.append(nonComparable[stuff]).append('\n');
        System.out.println(sb);
    }

    static void dijkstra(int start, int[] distance) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        distance[start] = 0;
        queue.offer(new Edge(start, 0));
        while(!queue.isEmpty()) {
            Edge cur = queue.poll();
            if(distance[cur.stuff] < cur.distance) continue;
            for(int stuff : map.get(cur.stuff)) {
                if(distance[stuff] > distance[cur.stuff] + 1) {
                    distance[stuff] = distance[cur.stuff] + 1;
                    queue.offer(new Edge(stuff, distance[stuff]));
                }
            }
        }
    }

    static class Edge implements Comparable<Edge> {
        int stuff, distance;
        public Edge(int stuff, int distance) {
            this.stuff = stuff;
            this.distance = distance;
        }
        @Override
        public int compareTo(Edge e) {
            return this.distance - e.distance;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 비교 결과들을 이용해 가벼운 물건에서 무거운 물건으로 간선을 이어 그래프를 생성합니다.
• 각 물건에서 자신을 제외한 다른 모든 물건으로의 최단 거리를 저장할 2차원 배열 distances를 생성하고 모든 값을 INF로 채웁니다.
• 각 물건에 다익스트라 알고리즘을 적용하여 다른 물건으로의 최단 거리를 구하고 이를 distances에 저장합니다.
• distances 배열에서 아래와 같은 경우를 찾습니다.
  • distances[s1][s2] = INF, distances[s2][s1] = INF
• distances[x][y]가 INF가 아니라면 y가 x보다 무겁다는 뜻이며, INF라면 두 물건은 비교 결과를 알 수 없음을 뜻합니다.
• distances[s1][s2]를 통해 s2가 s1보다 무거운지 확인하고, distances[s2][s1]을 통해 s1이 s2보다 무거운지 확인하여 두 경우에서 모두 비교 결과를 알 수 없음을 뜻하는 INF가 나온다면 비교 결과를 알 수 없는 물건의 개수를 1 증가시킵니다.