<aside> 🔥 이코테 38번 문제

</aside>

<aside> 🔥 문제 정리

n명의 학생수, 성적을 비교한 횟수 m이 주어지고

m개의 줄에 두 학생의 성적을 비교한 결과를 나타내는 a, b가 주어진다.

순위를 정확하게 알 수 있는 학생이 몇명인지 출력하라.

</aside>

<aside> 🔥 접근 방법

일단 나는 이 문제를 실패했다. 처음에는 플로이드 워셜 알고리즘으로 접근해서

거리 테이블에서 한 노드가 모든 노드에 갈 수 있는 즉 무한의 거리값이 없는 노드를 찾으려고 했는데

풀이를 확인해보니 아이디어는 비슷했으나 위 문제는 단방향으로 연결되어 있기 때문에

행 뿐만아니라 열도 확인해줬어야 했다. 아이디어는 아래와 같다.

플로이드 워셜 알고리즘 진행

1. 입력값을 토대로 2차원 테이블 생성

2. 자기 자신에게 가는 비용 0으로 업데이트

3. 간선 업데이트

4. 점화식으로 경로 업데이트

5. 여기서 행과 열을 모두 확인해서 모든 노드에 갈 수 있다면 순위를 모두 아는 노드인 것.

   

</aside>

<aside> 🔥 코드 진행

1. 플로이드 워셜 알고리즘 작성

   import sys
   
   with open('정확한 순위.text') as f:
       print("*" * 80, f.name)
       INF = int(1e9)
       sys.stdin = f
       input = sys.stdin.readline
   
       N, M = map(int, input().split())
       dist = [[INF] * (N + 1) for _ in range(N + 1)]
   
       for idx in range(1, N + 1):
           dist[idx][idx] = 0
   
       for _ in range(M):
           a, b = map(int, input().split())
           dist[a][b] = 1
   
       for k in range(1, N + 1):
           for a in range(1, N + 1):
               for b in range(1, N + 1):
                   dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])
   

2. 현재 노드를 기준으로 다른 노드로 갈 수 있는지 확인

   위를 정확하게 확인하려면 현재노드에서 다른 노드로 갈 수 있는지와

   다른 노드에서 현재 노드로 올 수 있는지도 확인해야한다.

   result = 0
   for cur in range(1, N + 1):
       cnt = 0
       # 현재 노드(cur)를 기준으로,
       # 다른 노드(node)로 갈 방법이 있는지 센다.
       for node in range(1, N + 1):
           if dist[cur][node] != INF or dist[node][cur] != INF:
               cnt += 1
       # 모든 노드에 대해 갈 수 있다면 순위를 아는 것.
       if cnt == N:
           result += 1
   print(result)
   

</aside>