문제설명

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과이다. A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다. 순위를 정확히 알 수 있는 학생이 있다.
예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮다. 따라서 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있다. 4번 학생은 2번 학생과 6번 학생보다 성적이 낮다. 즉, 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있다.
학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하는 프로그램을 작성하라.

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

접근

예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮다... 4번 학생은 2번 학생과 6번 학생보다 성적이 낮다... 즉, 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있다.
특정학생을 제외한 나머지 학생이 특정학생의 위 또는 아래로 명확히 구분되면 특정학생의 정확한 순위를 알 수 있음 > 특정학생(예시에서는 4번 학생)을 기준으로 그 학생보다 높은 순위인지 낮은 순위인지 구분을 할 수 있는 경우는 두가지의 경우가 존재함 > 1) 간접적 2) 직접적 >
4번 학생을 제외한 모든 학생으로부터 4번 학생으로의 경로가 존재하는지 알아야함 > N <= 500 이므로 플로이드 워셜 알고리즘을 사용할 수 있음 > 1)간접적 경로를 어떻게 표현할 것 인가? 간접적 경로(특정 학생을 거쳐가는 경로)를 직접적인 경로로 치환하여 경로 존재 자체의 유무를 표현할 수 있음 (예시. 1->5->4 의 경우 1->4 의 경우로 치환하여 표현. 즉, graph[1][4] = min(graph[1][4], graph[1][5] + graph[5][4]) 의 식을 통해 직접적 경로가 있는 것처럼 표현이 가능함) >
A번 학생에서 B번 학생으로의 경로가 있거나, 정반대의 경로가 존재하면 '성적 비교'가 가능함 > 양방향의 경로 모두 고려해야함

풀이

INF = int(1e9)

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

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 = 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)

배운점

두 지점 사이의 경로 유무를 판단할때, 플로이드 워셜 알고리즘을 이용하여 그것을 표현할 수 있다.