플로이드-워셜 연습 - 정확한 순위(이코테 38)

이코테 38번 문제

학생 N명에 대한 성적을 분실했는데, 다만 두 명씩 성적을 비교한 결과 M 개가 있다.

예를 들어 1~6번 학생이 있는데, 

1 < 5,

3 < 4, ...  이런 식으로 정보가 주어진다.

이 정보들만으로 확실히 성적 순위를 알 수 있는 학생은 몇 명일까? 

 

느낀 점

플로이드 워셜을 최단거리 구하는 데만 사용하다가, 이렇게 살짝 다른 방식(순위 결정)에 적용하려니까 나는 어려웠다.ㅎㅎ

그런데 이 문제를 공부하고 나니까, 플로이드 워셜의 조금 더 본질적인 부분을 살짝 느낄 수 있었던 것 같아서, 개인적으로는 마음에 드는(?) 고마운 문제다!🤓

이 문제에서 필요한 작업은 각 노드가 다른 노드들과 대소비교가 가능한가가를 알아내야 하는 문제였는데, 이때 다른 노드를 매개물로 삼아보는 과정이 필요하다. 플로이드 워셜을 처음 접할 때, 그리고 다익스트라와 묶어서 공부하면서 만난 전형적인 문제들이 주로 '최단 거리'와 연관되다보니 '최소'를 찾는게 중요한 거라고 느꼈던 것 같다. 그런데 이 문제를 공부해보니 '매개물'을 사용한다는 게 플로이드 워셜이 가진 더 본질적인 아이디어인 것 같다는 생각이 들었다.

INF = int(1e9)

n, m = map(int, input().split())
dis = [[INF] * (n+1) for _ in range(n+1)]

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

# 자신보다 성적이 높은 아이들(자기와 대소비교가 가능한 아이들)이라고 입력에 주어진 것을 반영
for _ in range(m):
    a, b = map(int, input().split())
    dis[a][b] = 1

# k 라는 커서가 하나씩 노드들을 돌면서, 매개물의 역할을 해본다.
for k in range(1, n+1):
    # a 와 b 가 대소비교 가능할까? 를 생각해주는 것. 만약 매개물을 통해서라도 대소비교가 가능하다면 INF 가 아닌 값으로 갱신.
    for a in range(1, n+1):
        for b in range(1, n+1):
            dis[a][b] = min(dis[a][b], dis[a][k] + dis[k][b])

result = 0
# 모든 노드들을 매개물로 삼아봐서 테이블 갱신이 완료되었으니


for cur in range(1, n+1):
    cnt = 0
    for node in range(1, n+1):
        # 각 노드들마다 - 자기노드(cur)행에서 특정 노드(node) 보다 점수 낮다는 정보가 있거나,
        # 아니면 특정노드(node)행에서 자기노드(cur)보다 점수가 낮다는 정보가 있다면,
        if dis[cur][node] != INF or dis[node][cur] != INF:
            # 그 노드와는 대소비교가 가능한 것. 자기노드행에서 그런 아이들 개수를 세어줌.
            cnt += 1
    # 그렇게 대소비교가능한 친구가 모든 노드개수와 같다면, 자신의 순위를 정확히 아는 것.
    # 순위를 아는 노드를 발견했으니 result +=1
    if cnt == n:
        result += 1
print(result)