백준 10159번 <저울>

백준 알고리즘 10159번

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

10159번: 저울

---

10159번

무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 비교 결과가 모순되는 입력은 없다고 가정한다.

물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하세요. 

---

문제 해결

어떻게 문제를 풀어야할지 고민하다가 재귀 함수를 이용해 풀기로 결정했다.

물건의 개수가 최대 100개이기때문에 각 물건마다 아무리 재귀 함수로 타고 들어가도 100번까지만 간다. 즉, 최대 100 * 100 으로 계산 가능하다고 생각했다.

 

재귀 함수로 각 물건 마다 작은 물건(schk)과 큰 물건(lchk)를 구했다. 그러면 각 물건마다 작은 물건의 개수(sdp)와 큰 물건의 개수(ldp)를 구할 수 있다.

 

각 물건마다 비교 결과를 알 수 없는 물건은 `물건의 개수(N) - 작은 물건의 개수(sdp) - 큰 물건의 개수(ldp) -1(자기자신)`이 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class BOJ_10159 {
    static int[] sdp, ldp;
    static boolean[] svisit, lvisit;
    static boolean[][] schk, lchk;
    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());
        ArrayList<Integer>[] Small = new ArrayList[N + 1];   // Smail[i] : i보다 작은 것들
        ArrayList<Integer>[] Large = new ArrayList[N + 1];   // Large[i] : i보다 큰 것들
        for (int i = 0; i < N + 1; i++) {
            Small[i] = new ArrayList<>();
            Large[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            String[] inArr = br.readLine().split(" ");
            int a = Integer.parseInt(inArr[0]);
            int b = Integer.parseInt(inArr[1]);

            Small[a].add(b);
            Large[b].add(a);
        }
        // end input

        sdp = new int[N + 1];
        ldp = new int[N + 1];
        schk = new boolean[N + 1][N + 1];
        lchk = new boolean[N + 1][N + 1];
        svisit = new boolean[N + 1];
        lvisit = new boolean[N + 1];
        for (int i = 1; i < N + 1; i++) {
            recursion(i, schk, svisit, Small);
            sdp[i] = count(schk[i]);
            recursion(i, lchk, lvisit, Large);
            ldp[i] = count(lchk[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N + 1; i++) {
            int answer = N - 1 - sdp[i] - ldp[i];
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }

    static boolean[] recursion(int num, boolean[][] chk, boolean[] visit, ArrayList<Integer>[] arr) {
        if (arr[num].size() == 0) return chk[num];
        visit[num] = true;
        for (int n : arr[num]) {
            if (visit[n]) {
                chk[num] = or(chk[num], chk[n]);
            } else {
                chk[num] = or(chk[num], recursion(n, chk, visit, arr));
            }
            chk[num][n] = true;
        }
        return chk[num];
    }

    static boolean[] or(boolean[] a, boolean[] b) {
        for (int i = 0; i < a.length; i++) {
            if (b[i]) a[i] = true;
        }
        return a;
    }

    static int count(boolean[] chk) {
        int cnt = 0;
        for (int i = 1; i < chk.length; i++) {
            if (chk[i]) cnt++;
        }
        return cnt;
    }
}

---

결과

 

---