문제
선생님은 시험을 본 학생 N명의 성적을 분실하였고, 성적을 비교한 결과의 일부만 가지고 있다.
학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과이다.
1번 학생의 성적 < 5번 학생의 성적
3번 학생의 성적 < 4번 학생의 성적
4번 학생의 성적 < 2번 학생의 성적
4번 학생의 성적 < 6번 학생의 성적
5번 학생의 성적 < 2번 학생의 성적
5번 학생의 성적 < 4번 학생의 성적 이를 통해 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있다.
예를 들어 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있고, 4번 학생은 2번 학생과 6번 학생보다 성적이 낮으므로
정리하면, 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있다.
하지만, 예시에서 4번 학생을 제외한 다른 학생은 정확한 순위를 알 수 없다. 학생들의 성적을 비교한 결과가 주어질 때,
성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하라.
입력
첫째줄에 n과 m 입력됨, 다음 m개의 줄에는 두 학생의 성적을 비교하는 a와 b 입력됨(a < b)
출력 : 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력
이 문제의 경우 A에서 B로 도달이 가능하거나, B에서 A로 도달이 가능하면 성적 비교가 가능한 것이다.
특정 노드에서 출발하여 다른 노드로 가는 최단 경로를 구하는 경우에는 다익스트라 알고리즘을
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구해야 하는 경우에는 폴로이드 워셜 알고리즘을 사용한다.
dijkstra(start)를 구현한 후 for start in range(1,n+1) 반복문을 돌리는 것보다 폴로이드 워셜 알고리즘을 사용하는 것이
더 간결하게 코드를 작성할 수 있다!!
일반적인 폴로이드 워셜 알고리즘의 경우 모든 노드에 대하여 다른 노드와의 최단 거리 값을 구하는 데 목적을 둔다면,
이 문제에서 사용되는 폴로이드 워셜 알고리즘은 최단 거리가 1이든 2 이든 중요하지 않고 INF인지 아닌지를 판단하는 데에 목적을 둔다. (도달이 가능한지 아닌지에 목적을 둠)
풀이
# 17-38) 정확한 순위
# 풀이 1
import sys
n, m = map(int, sys.stdin.readline().split())
cnt = 0
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for x in range(1, n+1): graph[x][x] = 1
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a][b] = 1
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if i == j: continue
if graph[i][k] == 1 and graph[k][j] == 1:
graph[i][j] = 1
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][j] == 1: graph[j][i] = 1
for v in graph:
if v.count(1) == n: cnt += 1
print(cnt)
# 풀이 2
import sys
INF = int(1e9)
n, m = map(int, sys.stdin.readline().split())
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
for x in range(1, n+1): graph[x][x] = 1
for _ in range(m):
a, b = map(int, sys.stdin.readline().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])
# graph의 값이 1이든 2이든 INF만 아니라면 도달 가능한 것이므로 상관없다!
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[i][j] != INF:
count += 1
if count == n:
result += 1
print(result)