이코테 책 387p

문제

• 시간제한
  • 1초
• 입력
  • 첫째줄에 학생의 수 N과 두 학생의 성적을 비교한 횟수 M
    • 2 <= N <= 500
    • 2 <= M <= 10,000
  • 둘째줄에 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B. (A번 학생의 B번보다 낮다는 뜻)
• 출력
  • 성적순위를 정확히 알 수 있는 학생이 몇 명인지 출력

선생님은 성적을 비교한 결과의 일부만 가지고 있다.
ex)
1번학생 성적 < 5번학생 성적
3번학생 성적 < 6번학생 성적
이렇게 성적을 1:1로 비교한 결과가 주어질때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하시오.

풀이

풀이 아이디어

이렇게 A가 B보다 낮다 = A->B의 경로 로 나타낼 수 있다.

• X->Y 나 Y->X가 도달이 가능하면 '성적비교'가 가능한 것.
• 도달이 불가능하면 '성적비교 결과를 알 수 없는' 것.
• n개 원소가 있을때, 최종 weight가 n이라면 처음부터 끝까지 연결되어있다는 것 = 순위를 알 수 있다는 것 이다.

모든 vertex에서의 모든 vertex의 weight를 알아야하기때문에 플로이드워셜을 사용한다.

시간복잡도

플로이드워셜의 복잡도는 O($N^3$)
학생수 N<=500 이므로 시간 내 동작이 가능하다.

코드

INF  = int(1e9)

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

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1) :
	for b in range(1, n+1) :
		if a == b :
			graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m) :
	# A에서 B로 가는 비용을 1로 설정 (=연결되어있다)
	a, b = map(int, input().split())
	graph[a][b] = 1

# 점화식에 따라, 플로이드 워셜 알고리즘을 수행
for k in range(1, n+1) :
	for a in range(1, n+1) :
		for b in range (1, n+1) :
			graph[a][b] = min(graph[a][b] , graph[a][k], graph[k][b])

result = 0
# 각 학생을 번호에 따라 한명씩 확인하며 도달 가능한지 체크
for i in range(1, n+1) :
	count = 0
	for j in range(1, n+1) :
		if graph[i][j] != INF or graph[j][i] != INF :
			count += 1
	if count == n:
		result += 1

print(result)