저울의 무게 비교를 그래프로 바꿔서 최단 거리 알고리즘으로 해결(플로이드 워셜, 그래프 탐색)

1. 문제

 

10159번: 저울 (acmicpc.net)

10159번: 저울

 

2. 풀이

 

그냥 보면 어떻게 해야할지 감 잡기가 쉽지 않다..

 

하지만 "2 > 3, 3 > 4로부터 2 > 4라는 것을 알 수 있다"를 봤을때,

 

1 > 2, 2 > 3, 3 > 4, 5 > 4, 6 > 5를 마치 방향 그래프에서 간선으로 보면 2에서 4로 도달할 수 있는가? 아닌가를 체크하면 되는 문제이다.

 

사실 뭐 최단 거리를 묻는 것은 아니므로 BFS나 DFS로 탐색하면 해결할 수 있겠지만.. N이 100이하이니 $O(N^{3})$ 플로이드 워셜로 충분히 가능할 것이다.

 

i > j이면, 그래프에 graph[i][j] = 1로 저장한다.

 

플로이드 워셜 알고리즘을 수행하여, 거리가 INF가 아니라면 i에서 j로 도달할 수 있으므로 카운팅 해준다.

 

근데 graph[i][j]는 i > j인가?를 체크하는 것인데.. i와 j의 무게를 비교하는 것은 i < j도 있으니까, graph[j][i]도 INF인지 아닌지 체크해줘야한다.

 

from sys import stdin

INF = 10000000000000000

def floyd(graph):

    for i in range(1,n+1):

        graph[i][i] = 0

    for k in range(1,n+1):

        for i in range(1,n+1):

            for j in range(1,n+1):

                if graph[i][j] > graph[i][k] + graph[k][j]:

                    graph[i][j] = graph[i][k] + graph[k][j]

    return graph    

n = int(stdin.readline())

m = int(stdin.readline())

graph = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(m):
    
    i,j = map(int,stdin.readline().split())

    graph[i][j] = 1

graph = floyd(graph)

for i in range(1,n+1):
    
    count = 0

    for j in range(1,n+1):
        
        if graph[i][j] == INF and graph[j][i] == INF:
            
            count += 1
    
    print(count)

 

3. 풀이2

 

어쨌든 i에서 j로 도달할 수 있는가? 반대로 j에서 i로 도달할 수 있는가?를 체크하면 되므로 BFS로도 가능하다.

 

순방향 graph1을 만들고 간선을 뒤집은 역방향 graph2를 만든 다음,

 

각 그래프에서 i번에서 시작하는 BFS를 수행해서 어떤 정점에 도달할 때마다 카운팅을 해준다.

 

전체 n개에서 자기 자신 뺀 n-1개에서 각 BFS에서 도달한 정점의 수를 빼주면 될 것

 

from collections import deque
from sys import stdin

def bfs(s,graph):
    
    queue = deque([s])

    visited = [0]*(n+1)

    visited[s] = 1

    count = 0

    while queue:
        
        v = queue.popleft()

        for u in graph[v]:
            
            if visited[u] == 0:
                
                count += 1
                visited[u] = 1
                queue.append(u)
        
    return count
                
n = int(stdin.readline())

m = int(stdin.readline())

graph1 = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]

for _ in range(m):
    
    i,j = map(int,stdin.readline().split())

    graph1[i].append(j)
    graph2[j].append(i)

for i in range(1,n+1):
    
    print(n-1 - (bfs(i,graph1) + bfs(i,graph2)))