[백준] #2458 키 순서(python)

📌문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

1번 학생의 키 < 5번 학생의 키
3번 학생의 키 < 4번 학생의 키
5번 학생의 키 < 4번 학생의 키
4번 학생의 키 < 2번 학생의 키
4번 학생의 키 < 6번 학생의 키
5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. 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 (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

예제 입력1

6 6
1 5
3 4
5 4
4 2
4 6
5 2

예제 출력1

1

예제 입력2

6 7
1 3
1 5
3 4
5 4
4 2
4 6
5 2

예제 출력2

2

예제 입력3

6 3
1 2
2 3
4 5

예제 출력3

0

백준 2458번 문제

💡Idea

아래의 조건을 만족하는 경우, 자신의 키가 몇 번째인지 알 수 있습니다.

자신으로 올 수 있는 노드의 개수 $+$ 자신이 갈 수 있는 노드의 개수 $= N - 1$

• 자신으로 올 수 있는 모든 노드들은 자신보다 키가 작은 학생들이고, 자신이 갈 수 있는 모든 노드들은 자신보다 키가 큰 학생들을 뜻합니다.

• 자신보다 키가 작은 학생들의 수와 키가 큰 학생들의 수를 더한 값이 $N - 1$이 된다면 전체 학생들과 자신을 각각 비교한 것이기 때문에 자신의 키가 몇 번째인지를 알 수 있습니다.

📌플로이드 워샬

자신으로 올 수 있는 노드와 갈 수 있는 노드의 개수를 구하기 위해서는 연결이 되어 있는가를 확인하는 용도의 플로이드 워샬을 사용하면 됩니다.

예를 들어, 문제의 예시로 나와있는 그래프를 플로이드 워샬의 이차원 리스트로 표현하면 다음과 같습니다.

리스트의 [a][b]에는 a에서 b로 갈 수 있는 경우에는 1, 아니면 0이 들어있습니다.

예시를 보면, 1은 5로, 5는 2로 갈 수 있어 각각의 값이 1인 것을 확인할 수 있습니다. 이 때, 1은 2로도 갈 수 있으므로 해당 값도 1이 됩니다.

이런 식으로 리스트의 값을 통해 자신에게 올 수 있는 노드의 개수와 자신이 갈 수 있는 노드의 개수를 확인할 수 있습니다.

💻코드

• ⏰ 시간 : 1148 ms / 메모리 : 117276 KB
• 이 문제는 pypy3으로 제출해야 시간 초과없이 통과됩니다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = 1

# 플로이드 워샬
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            if graph[j][i] == 1 and graph[i][k] == 1: #j에서 i, i에서 k로 연결되어 있는 경우
                graph[j][k] = 1 # j에서 k로 연결

ans = 0
for i in range(1, N + 1): # 각 노드가 몇 번째 인지를 알 수 있는지 확인
    value = 0
    for j in range(1, N + 1):
        value += graph[i][j] + graph[j][i] # 자신으로 오거나 자신이 갈 수 있는 노드 개수 더함
    if value == (N - 1): ans += 1
print(ans)