[ BOJ ] 10159 : 저울 ( GOLD 4 ) / Python

문제

무게가 서로 다른 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 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

풀이 과정

물건들의 무게 비교 결과가 주어지면, 1번보다 가벼운 2번, 3번, 4번.. 이라던지, 4번보다 무거운 5번, 6번... 등 무게 관계가 마치 연결되어 있는 것처럼 보인다. 그렇다고 무작정 양방향 간선으로 그래프 탐색을 돌려버린다면, 1번 물건은 무게 관계를 정확히 모르는 6번 물건까지 결과를 아는 것처럼 출력되어버린다.

 

중요한 아이디어는, 특정 물건보다 무거운 것들을 탐색하고 따로 가벼운 것들을 한 번 더 탐색하는 것이다. 더 무거운 물건들만 먼저 탐색하고 더 가벼운 물건을 나중에 따로 탐색하면 무게 비교 관계가 겹치지 않고 관계를 알 수 있는 물건들의 여부를 확인할 수 있다.

 

더 무겁고 관계를 확인 가능한 물건들이 얼마나 있고, 더 가볍고 관계를 확인 가능한 물건들이 얼마나 있는지만 확인하면 되기 때문에 다양한 탐색 알고리즘으로 풀이가 가능하다. 필자는 BFS, Dijkstra, Floyd-Warshall 방식으로 풀이했다.

Python ( BFS )

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().rstrip())
big_graph = [{} for _ in range(n+1)]
small_graph = [{} for _ in range(n+1)]
m = int(input().rstrip())
for _ in range(m):
    a, b = map(int, input().rstrip().split())
    big_graph[a][b] = 1
    small_graph[b][a] = 1

def big_bfs(start, end):
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    queue = deque()
    queue.append(start)

    while queue:
        now = queue.popleft()

        if now == end:
            return 1
        
        for next, _ in big_graph[now].items():
            if visited[next] == 0:
                visited[next] = 1
                queue.append(next)

    return 0

def small_bfs(start, end):
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    queue = deque()
    queue.append(start)

    while queue:
        now = queue.popleft()

        if now == end:
            return 1
        
        for next, _ in small_graph[now].items():
            if visited[next] == 0:
                visited[next] = 1
                queue.append(next)

    return 0

for i in range(1, n+1):
    cnt = 0
    for j in range(1, n+1):
        if i == j: continue
        if big_bfs(i, j) == small_bfs(i, j) == 0:
            cnt += 1
    print(cnt)

Python ( Dijkstra )

import sys
import heapq
input = sys.stdin.readline

n = int(input().rstrip())
big_graph = [{} for _ in range(n+1)]
small_graph = [{} for _ in range(n+1)]
m = int(input().rstrip())
for _ in range(m):
    a, b = map(int, input().rstrip().split())
    big_graph[a][b] = 1
    small_graph[b][a] = 1

def big_dijkstra(start):
    distances = {node:float('inf') for node in range(n+1)}
    distances[start] = 0

    queue = []
    heapq.heappush(queue, (0, start))

    while queue:
        current_distance, current_destination = heapq.heappop(queue)

        if distances[current_destination] < current_distance: continue

        for next_destination, next_distance in big_graph[current_destination].items():
            distance = current_distance + next_distance
            if distance < distances[next_destination]:
                distances[next_destination] = distance
                heapq.heappush(queue, (distance, next_destination))
    
    return distances
def small_dijkstra(start):
    distances = {node:float('inf') for node in range(n+1)}
    distances[start] = 0

    queue = []
    heapq.heappush(queue, (0, start))

    while queue:
        current_distance, current_destination = heapq.heappop(queue)

        if distances[current_destination] < current_distance: continue

        for next_destination, next_distance in small_graph[current_destination].items():
            distance = current_distance + next_distance
            if distance < distances[next_destination]:
                distances[next_destination] = distance
                heapq.heappush(queue, (distance, next_destination))
    
    return distances

for i in range(1, n+1):
    result1 = list(big_dijkstra(i).values())
    result2 = list(small_dijkstra(i).values())

    cnt = 0
    for i in range(1, n+1):
        if result1[i] == result2[i] == float('inf'):
            cnt += 1
    
    print(cnt)

Python ( Floyd-Warshall ) 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
big_graph = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
small_graph = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
m = int(input().rstrip())
for _ in range(m):
    a, b = map(int, input().rstrip().split())
    big_graph[a][b] = 1
    small_graph[b][a] = 1

for i in range(1, n+1):
    big_graph[i][i] = 0
    small_graph[i][i] = 0

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            big_graph[a][b] = min(big_graph[a][b], big_graph[a][k] + big_graph[k][b])
            small_graph[a][b] = min(small_graph[a][b], small_graph[a][k] + small_graph[k][b])

for i in range(1, n+1):
    cnt = 0
    for j in range(1, n+1):
        if i == j: continue
        if big_graph[i][j] == small_graph[i][j] == float('inf'):
            cnt += 1
    print(cnt)