정확한 순위

문제 요약:

이문제는 이코테 책 Q38번 문제로 학생수n, 그리고 성적비교 결과개수 m개 가 주어진 뒤,

성적이 두명중에서 누가 위인지만 m개의 결과를 알려준 후,

성적 순위를 정확히 알 수 있는  학생은 모두 몇 명인지 계산하는 프로그램을 작성

이코테 난이도 2

 

소요시간 :

18분

 

1차시도:

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
INF = int(1e9)
arr = [[INF]*n for _ in range(n)]
for _ in range(m):
	s,e = map(int,input().split())
	arr[s-1][e-1] = 1
	
#플로이드 워셜
for k in range(n):
	for y in range(n):
		for x in range(n):
			if arr[y][x] > arr[y][k] +arr[k][x]:
				arr[y][x] = arr[y][k] +arr[k][x]
ans = 0
	
for k in range(n):
	icango = n - arr[k].count(INF) 
	ucango = n - list(zip(*arr))[k].count(INF)
	if icango + ucango == n-1:
		ans +=1

print(ans)

위상정렬이고, 이는 n이 500이하 이므로 플로이드 워셜(O(n^3))을 해도 시간내에 풀 수 있다는것을 확인한 뒤 들어갔다.

쉽게 말하면 여기서 성적순위를 알수 있는 학생은 플로이드 워셜 진행후, 내가 갈수있는(이긴) 학생수와 나한테 올수있는(지는) 학생수의 합이 n-1개라면 (나를 제외한 숫자) 성적순위를 알 수 있다고 생각했다.