[BOJ] 백준 10159번 : 저울 (JAVA)

문제

무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)

 

[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]

 

우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다. 

 

비교 결과가 모순되는 입력은 없다고 가정한다. 위 예제의 기존 측정 결과에 [3]>[1]이 추가되었다고 가정하자. 이 경우 [1]>[2], [2]>[3]이므로 우리는 [1]>[3]이라는 것을 예측할 수 있는데, 이는 기존에 측정된 결과 [3]>[1]과 서로 모순이므로 이러한 입력은 가능하지 않다. 

 

물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하는 프로그램을 작성하시오.

 

 

입력

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

 

 

출력

여러분은 N개의 줄에 결과를 출력해야 한다. i 번째 줄에는 물건 i 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

 

 

풀이

2458번 키 순서 문제와 거의 일치하는 문제였습니다. 이 문제의 해설에 대한 포스팅은 아래 링크에서 참조하실 수 있습니다.

 

 

[BOJ] 백준 2458번 : 키 순서 (JAVA)

 

 

키 순서 문제와 유사하게 이번에는 무게를 비교해야 합니다. 그리고 특정 물건에 대하여 무게를 비교할 수 없는 물건의 개수를 구해야 했습니다.

 

이를 해결하기 위해서는 모든 정점에서 모든 정점으로 이동할 수 있는지 여부를 구하는 플로이드 와샬 알고리즘을 사용해야 합니다.

 

다만, 문제에서는 단방향 그래프로 입력이 주어졌기때문에 2가 3보다 무게가 가볍더라도 플로이드 와샬 알고리즘을 수행한 배열 상으로는, 3에서 2로 이동할 수 없기때문에 2가 3보다 작은지 판단할 수 없는 문제가 생깁니다.

 

우선, 이를 방지하는 전반적인 로직부터 소개하겠습니다.

 

 

1. 문제의 입력을 받은 배열에 대하여 플로이드 와샬 알고리즘을 취한다.

2. 문제의 입력과 반대로 받은 배열에 대하여 플로이드 와샬 알고리즘을 취한다.

3. 1번과 2번의 배열 or 연산한다.

4. or 연산한 배열에서 자신은 제외한 학생 모두를 탐색할 수 있는 인덱스의 개수를 계산한다.

 

 

2번과 3번 과정을 취한 이유는 간단합니다.

특정 물건보다 작은 물건 쪽으로도 길을 만들어주기 위함입니다.

 

이 과정에서 특정 물건에 대하여 비교할 수 있는 물건은 자기 자신을 제외하고는 모두 true로 처리될 것입니다.

따라서, 우리는 or 연산한 배열에서 false가 몇 개인지 체크만 해 주면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
 
        // 문제에서 주어진대로 입력을 받음.
        boolean[][] arr = new boolean[N + 1][N + 1];
 
        // 문제에서 주어진 것과 반대로 입력을 받음.
        boolean[][] reverse_arr = new boolean[N + 1][N + 1];
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
 
            arr[x][y] = true;
            reverse_arr[y][x] = true;
        }
 
        // 플로이드 와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][k] && arr[k][j]) {
                        arr[i][j] = true;
                    }
 
                    if (reverse_arr[i][k] && reverse_arr[k][j]) {
                        reverse_arr[i][j] = true;
                    }
                }
            }
        }
 
        // 특정 물건에 대하여 더 무거운 물건과 더 가벼운 물건 모두를 파악 가능.
        // 만약 |을 취한 값이 false라면, 그 물건과 무게 비교를 할 수 없다는 의미.
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] |= reverse_arr[i][j];
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            int cnt = 0;
            for (int j = 1; j <= N; j++) {
                if (i == j) { // 자기 자신은 제외.
                    continue;
                }
 
                // 무게 비교를 할 수 없을 경우 cnt 증가.
                if (!arr[i][j]) {
                    cnt++;
                }
            }
 
            sb.append(cnt + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.