Chap 17. 최단경로 - Q38. 정확한 순위

@mildsalmon·2021-11-24 22:53

1. 정확한 순위

난이도
- 중
풀이 시간
- 40분
시간 제한
- 1초
메모리 제한
- 128MB

A. 📜 문제

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

1번 학생의 성적 < 5번 학생의 성적
3번 학생의 성적 < 4번 학생의 성적
4번 학생의 성적 < 2번 학생의 성적
4번 학생의 성적 < 6번 학생의 성적
5번 학생의 성적 < 2번 학생의 성적
5번 학생의 성적 < 4번 학생의 성적

A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다.

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하는 프로그램을 작성하라.

a. 예를 들면.

순위를 정확히 알 수 있는 학생이 있다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮다. 따라서 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있다. 4번 학생은 2번 학생과 6번 학생보다 성적이 낮다. 즉, 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있다.

b. 입력 조건

첫째 줄에 학생들의 수 N (2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어진다.
다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B가 주어진다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미한다.

c. 출력 조건

첫째 줄에 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력한다.

d. 테스트 케이스

입력 예시
```
6 6
1 5
3 4
4 2
4 6
5 2
5 4
```
출력 예시
```
1
```

B. 💡 내 답안

a. 😊 1, 2차 시도 (성공)


"""
Date    : 2021.11.24
Update  : 2021.11.24
Source  : Q38_정확한 순위.py
Purpose : 플로이드 알고리즘을 사용하여 학생들의 성적 순위를 알 수 있는 경우를 구함
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# n = 학생들의 수
# m = 성적을 비교한 횟수
n, m = list(map(int, input().split()))
# 학생들의 성적 비교가 가능한 경우의 인접행렬
array = [[1e9]*(n+1) for i in range(n+1)]

# 초기 비교 횟수 입력
for i in range(m):
    A, B = list(map(int, input().split()))

    array[A][B] = 1

# 자기 자신과 비교하는 경우는 0으로 입력
for i in range(n+1):
    array[i][i] = 0

# i -> k -> j가 i -> j보다 작다면 값을 교체
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            array[i][j] = min(array[i][k] + array[k][j], array[i][j])

# print(*array, sep='\n')

result = 0

# A -> B인 경우와 B -> A인 경우 중 최단 거리를 구했다면, count를 증가시킴.
# count가 학생수와 같다면 결과값을 증가시킴.
for i in range(1, n+1):
    count = 0
    for j in range(1, n+1):
        if array[i][j] != 1e9 or array[j][i] != 1e9:
            count += 1
    if count == n:
        result += 1
print(result)

############
#### 플로이드로 안풀려서 다익스트라로 풀려고 했는데, cost 처리를 못함.
############

# from collections import deque
#
# n, m = list(map(int, input().split()))
#
# array = [[] for i in range(n+1)]
#
# distance = [0] * (n+1)
# q = deque()
#
# for i in range(m):
#     A, B = list(map(int, input().split()))
#
#     array[A].append(B)
#
# for i in range(n):
#     q.append(i)
#
# while q:
#     x = q.popleft()
#
#     for i in range(array[x]):
#         distance[x] += 1
#         distance[i] += distance[x]