[백준] 10159 저울 with Python

📌 BOJ 10159 저울

💡 조건

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

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

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

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

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

6. 플로이드 와샬 알고리즘 유형의 문제

🖥 소스 코드

from sys import stdin

n = int(stdin.readline())
m = int(stdin.readline())

arr = [[False] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    arr[a][b] = True


for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if arr[i][k] and arr[k][j]:
                arr[i][j] = True

for i in range(1, n + 1):
    cnt = 0
    for j in range(1, n + 1):
        if not arr[i][j] and not arr[j][i]:
            cnt += 1
    print(cnt - 1)

🔖 예제 및 실행결과

예제

9
11
2 1
3 1
2 8
2 9
7 8
4 5
6 7
6 3
1 7
6 2
1 9

실행결과

2
3
3
7
7
2
3
3
4

⌨️ 문제 풀이

1. 플로이드 와샬 알고리즘을 사용하여 푸는 문제이다. 문제를 참고해보면, N의 범위가 최대 100, M은 최대 2000 이다.
2. (1) 번을 다른 말로 해보자면, 노드가 최대 100개, 간선의 개수가 최대 2000개 입력을 받을 수 있다는 것이다.
3. 플로이드 와샬의 시간복잡도는 O(N^3) 이며, 이 문제에서는 최대 100 * 100 * 100 만큼의 연산이 필요하다는 것을 알 수 있다.
4. 물건 쌍의 비교결과를 입력받아 그래프에 입력하고, 이를 플로이드 와샬 알고리즘을 통해 서로 비교결과를 알 수 없는 것들을 출력하면 된다.