[알고리즘][Python] 백준(BOJ) 2458 키 순서_파이썬

 

2458 키 순서    www.acmicpc.net/problem/2458

2458번: 키 순서

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 탐색, 깊이 우선 탐색, 플로이드-와샬

 

 

 

 

 

 

 

풀이

<내용>

• 학생들의 키를 비교한 결과를 저장한다.
• 학생들의 키를 비교할 수 있는지 확인하는 check를 초기화한다.
• 1번 학생부터 dfs 함수를 돌면서 만약에 1번 학생보다 5번 학생이 작다면 1번과 5번, 5번과 1번 둘 다 비교할 수 있으므로 check에 저장한다.
• check를 돌면서 모든 학생들과 비교할 수 있어 자신의 키가 몇 번째인지 정확하게 알 수 있는 학생의 수를 계산한다.

 

 

<코드>

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, m = map(int, input().split())
height = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if b-1 not in height[a-1]:
        height[a-1].append(b-1)
        
def dfs(i, idx, height):
    for j in height[idx]:
        if not check[i][j]:
            check[i][j] = 1
            check[j][i] = 1
            dfs(i, j, height)
    
check = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    check[i][i] = 1
    dfs(i, i, height)
        
res = 0
for row in check:
    if row == [1]*n:
        res += 1
        
print(res)

 

+) 플로이드-와샬로도 해결 가능하다. → 다음에 풀이 추가