백준_2458_키순서/Using_Python_파이썬

문제

https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

About Problem

이 문제는 학생수와 비교 횟수를 주면서, 비교할 수 있는 사람 번호를 주기 때문에 간선 아래와 같이 간선 번호로 나타 낼 수 있다.

여기서 출려을 자신의 키가 몇 번째 인지 알 수 있는 학생들을 모두 구하라고 했으니 모든 정점에서 다른 모든 정점까지 최단 경로를 구할 수 있는 알고리즘인 플로이드 와샬을 썼다. 플로이드 와샬은 O(N^3)이므로 입력 값을 고려해서 쓰는 것이 좋다.

만약 빅오를 줄이려면 dfs를 모든 정점을 탐색 할 수 있고 가지치기로 시간을 줄 일 수 있는 DFS도 좋은 방법인 것 같다.

 

Code

주석에 코드에 대한 설명을 넣었다.

from sys import stdin

# 입력값 받기
N, M = map(int, stdin.readline().split())

# 키의 대소를 비교해주는 array
array = [[0] * (N+1) for _ in range(N+1)]

# 입력값을 통해서 array에 비교했던 것을 넣기
for _ in range(M):
    s, t = map(int, stdin.readline().split())
    array[s][t] = 1

# 플로이드 와샬 사용 정점과 정점사이 중간 정점을 통해서 모든 정점에서 다른 모든 정점의 최단거리 구하기
for k in range(1, N+1):
    for i in range(1, N+1):
        if k == i:
            continue
        for j in range(1, N+1):
            if i == j:
                continue
            if array[i][k] and array[k][j]:
                array[i][j] = 1
answer = 0

# 자신의 위치를 기준으로 자신보다 큰 사람, 작은 사람이 다 있으면 자신이 몇번 째 인지 판단가능
for i in range(1, N+1):
    num = 0
    for j in range(1, N+1):
        num += array[i][j] + array[j][i]
    if num == N-1:
        answer += 1
print(answer)