이것이 코딩테스트다 38 정확한 순위 (Python)

문제 링크

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과다.

• 1번 학생 → 5번 학생
• 3 → 4
• 4 → 2
• 4 → 6
• 5 → 2
• 5 → 4

A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다.
위에 제시된 정보를 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있다. 정리하면 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있지만 다른 학생은 정확한 순위를 알 수 없다.
학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 몇명인지 계산하는 프로그램을 구하시오.

입력조건 

• 첫째 줄에 학생들의 수 N(2 ≤ N ≤ 500)과 두 학생의 성적을 비교한 횟수 M(2 ≤ M ≤ 10,000)
• 다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B

---

Test Case

입력
6 6
1 5
3 4
4 2
4 6
5 2
5 4

출력
1

---

문제 풀이

처음에는 무슨 문제인지 잘 몰랐다가 그래프 그려보고 2차원 리스트 그려보고 무슨 문제인지 조금씩 파악이 가능했다. 그리고 문제에 주어진 예시가 조금 복잡해서 단순화 시켜서 좀 더 편하게 문제를 바라봤다.
이렇게 step by step 으로 생각해볼것
문제 다 풀고 다른 사람들 풀이를 봤는데 나처럼 2차원 그래프를 다 완성시킨게 아니었다.
나는 입력받은 데이터를 플로이드 와샬 알고리즘으로 최단거리 그래프를 완성시킨뒤 그 그래프를 a→b 구분이 없다고 생각해서 대칭형으로 만든 뒤 풀었는데 다른 사람들은 대칭으로 안 만들고 갈수있는지 없는지만 파악해서 풀었더라.

---

Source Code

import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int, input().split())

graph = [[INF] * (n+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if i == j:
            graph[i][j] = 0

for i 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])

for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j] == INF:
            graph[i][j] = graph[j][i]
        elif graph[j][i] == INF:
            graph[j][i] = graph[i][j]

cnt = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j] == INF:
            cnt += 1
            break
print(n-cnt)