문제풀이/BOJ
[Python] BOJ/백준 2458번 키 순서
서채리
2022. 8. 25. 23:33
[문제]
https://www.acmicpc.net/problem/2458
2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
[풀이]
두 학생 a, b를 a가 b를 향하는 방향 그래프로 나타내면 키의 크고 작음을 표시할 수 있다.
플로이드-와샬 알고리즘을 통해 한 정점에서부터 모든 정점으로의 연결 상태를 알아내어 그래프를 갱신한다.
왼쪽 리스트는 예제 2번 문제를 플로이드-와샬 알고리즘을 통해 그래프를 갱신한 상태이다. 위 그림의 1번 노드는 다른 정점을 통해 모든 정점으로 연결될 수 있기 때문에 리스트[0] 은 자기 자신을 제외하고 전부 1이다.
2번 노드는 자신으로부터 출발하는 정점이 없기 때문에 리스트[1] 은 전부 0의 값을 가진다.
이런식으로 각 노드와 연결된 노드의 개수가 N - 1이라면 해당 노드가 몇 번째인지 알 수 있다.
+ 이 문제는 pypy3으로 제출해야 통과된다.
++ 플로이드-와샬 알고리즘을 각 정점에서 다른 모든 정점으로 연결됐는지 여부를 확인하는 용도로는 처음 써보았다.
[코드]
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
student = [([0] * N) for _ in range(N)]
for _ in range(M):
small, tall = map(int, input().split())
student[small-1][tall-1] = 1
for k in range(N):
for i in range(N):
for j in range(N):
if student[i][k] == 1 and student[k][j] == 1:
student[i][j] = 1
answer = 0
for i in range(N):
check = 0
for j in range(N):
check += student[i][j] + student[j][i]
if check == (N - 1):
answer += 1
print(answer)