정확한 순위 K대회 최단거리

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

이를 유추해서 순위를 정확히 알 수있는 학생도 있고 알수 없는 학생도 있습니다. 순위를 정확히 알 수 있는 학생은 모두 몇명인가요?

해당 문제도 결국 최단 경로를 계산하는 문제로 볼 수 있다고 합니다. 비교 하는 것을 그래프로 볼 수 있는데 이때 A번 학생과 B번 학생을 비교할때 경로를 볼 수 있는데 A에서 B로 도달이 가능하거나 반대도 가능하면 성적 비교가 되지만 도달이 안되는 것은 곧 성적을 비교할 수 없는 상황이 됩니다.

모든 노드에 대해서 서로 도달이 가능한지 체크를 하고 자기 자신은 도달이 가능하다고 보고 카운트를 진행을 합시다. 결과적으로 특정한 노드의 카운트 값이 N이라면 해당 노드의 정확한 순위를 알 수 있다는 것을 의미 합니다.

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 개수, 간선의 개수를 입력받기
n,m = map(int, input().split())
#2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
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)

2차원 리스트를 만들고 0으로 초기화 한다음 각 간선에 대한 정보를 입력받아 해당 하는 값으로 초기화를 합니다. 이때 간선의 비용은 언급하지 않았으니 1이라고 해줍시다.

그리고 점화식에 따라서 플로이드 워셜 알고리즘을 수행합니다. 특정 노드에서 다른 노드까지 도달 할 수 있는지 최소 비용을 체크를 하게 됩니다.

그리고 각 학생을 번호에 따라 한명씩 확인하여 도달 가능한지 체크를 하게 됩니다.

예시로 아래처럼 주어졌을때

1-5

3-4

4-2

4-6

5-2

5-4

직접 계산을 해보면 4가 1부터 6까지 모두 도달이 가능한 유일한 학생임을 알 수 있습니다.