[백준] 2458 파이썬

문제

---

• 백준 2458 (골드 4)

백준 2458

학생들의 키를 비교한 결과를 통해서 전체에서 키가 몇번째인지 알 수 있는 학생의 수를 구하는 문제였다.
한달쯤 전에 풀었던 문제였는데 어떻게 접근해야될지 고민이 많았던 것이 지금까지도 기억이 났다.
입력이 최대 500이여서 시간 제한은 널널한 문제였다.

내 코드

---

두 개의 dfs 함수를 통해서 구현 가능할 것 같아 시도해보았다.
우선 처음 키를 비교한 결과를 받을 때 자신보다 큰 학생들은 big으로 작은 학생들은 small으로 나눠 받았다.
다음으로 각 학생마다 dfs_big과 dfs_small 두 가지 함수를 돌면서 자신보다 큰 학생, 자신보다 작은 학생의 수를 계산하였다.
계산된 학생의 수가 전체 학생과 같다면 결과를 하나씩 올려주었다.

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
big = [[] for _ in range(n+1)]
small = [[] for _ in range(n+1)]
visited = [False]*(n+1)
ans = 0
for _ in range(m):
    a, b = map(int,input().split())
    big[a].append(b)
    small[b].append(a)

def dfs_big(i):
    for x in big[i]:
        if not visited[x]:
            visited[x] = True
            dfs_big(x)

def dfs_small(i):
    for x in small[i]:
        if not visited[x]:
            visited[x] = True
            dfs_small(x)

for i in range(1, n+1):
    visited = [False]*(n+1)
    visited[0] = True
    visited[i] = True
    dfs_big(i)
    dfs_small(i)
    if False not in visited:
        ans += 1 

print(ans)

문제 해결 후에 다른 사람들의 코드를 확인해보니 플로이드-워셜 알고리즘을 활용하여서도 해결 가능하다는 것을 알 수 있었다.
문제를 보고 플로이드-워셜 알고리즘을 바로 떠올릴 수 있도록 더 많은 문제를 풀어봐야겠다는 생각이 들었다.