[BOJ/백준] 10159 저울

import sys
 
input = sys.stdin.readline
N = int(input())
M = int(input())
 
graph = [[0 for _ in range(N+1)] for i in range(N+1)]
visited = [[True for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1
 
 
 
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if start == end:
                continue
            if graph[start][mid] and graph[mid][end]:
                graph[start][end] = 1
 
result = []
for start in range(1,N+1):
    cnt = 0
    for end in range(1,N+1):
        if start == end:
            continue
        else:
            if not (graph[start][end] or graph[end][start]):
                cnt += 1
    result.append(cnt)
for row in result:
    sys.stdout.write(str(row)+'\n')

 

 

많이 해맸던 문제였다. 대소관계가 있는데 그걸 통해, 서로 비교가 불가능한 경우를 찾는 것을 어떻게 할지 고민을 많이했다.

 

플로이드 와샬을 통해 만들었다. 

 

대소 관계가 가능하다는 것은 

 

(1,2) (2,3) 이렇게 주어진다하면

 

그래프에서 graph[1][2],graph[2][3]에 1이 들어갈것이다.

 

그러면 플로이드 와샬을 통해, 두개의 그래프가 graph[start][mid], graph[mid][end] 가 전부 1이라고 했을때에만

 

start 가 end보다 크다는것을 알 수 있다.

 

이렇게 플로이드 와샬을 돌리고 난뒤에, 전체 N에 대해서 N번 돌려주면서, 서로 다른 두점의 그래프의 값이 전부 0이면, 

 

대소비교가 불가능한 경우이다. 이 경우를 전부 세어주면 문제를 풀 수 있다.