백준 2458. 키 순서

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

1. 플로이드-워셜 알고리즘 풀이

import sys

N, M = map(int, input().split())
height = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    tall, short = map(int, sys.stdin.readline().split())
    height[tall][short] = 1

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if height[i][j] == 1 or (height[i][k] == 1 and height[k][j] == 1): # 경로 k를 거치거나 안거쳐도 i->j로 갈 수 있으면
                height[i][j] = 1

ans = 0
for i in range(1, N+1):
    known_height = 0
    for j in range(1, N+1):
        known_height += height[i][j] + height[j][i] # 자신보다 작은사람과 큰사람의 합(0 + 1 or 1 + 0 or 0 + 0 -> 알 수 없음)
    if known_height == N-1: # 자신보다 작은사람과 큰사람의 합이 N-1이 되어야 모든 사람과 연결되는 것이므로 정답 조건 만족!
        ans += 1
print(ans)

2. dfs 풀이 -> 시간복잡도 훨씬 낮음!

import sys
input = sys.stdin.readline

def dfs(now, idx):
    for node in arr[idx]: 
        if visited[now][node] == 0 : 
            visited[now][node]= 1 # 연결되어있음을 확인하는 1
            visited[node][now]= 1 
            dfs(now,node) 

n, m = map(int,input().split())
arr = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int,input().split())
    arr[a].append(b)

visited = [[0]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    visited[i][i] = 1
    dfs(i,i)

cnt = 0

for i in range(1,n+1):
    if sum(visited[i]) == n : # 나보다 크거나 작은 사람 + 나 = n이면 정답 조건 만족!
        cnt += 1

print(cnt)