[백준] 2458번 : 키 순서

2458번: 키 순서

🤔 문제분석

플로이드 워셜로 문제를 접근하면 됩니다. s에서 g로 갈 수 있는 경로가 존재한다는것을 모두 파악한 뒤에 해당 그래프가 다른 그래프와 모두 연결되어있는지 확인하면 됩니다.

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

arr = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    small, big = map(int,input().split())
    arr[big][small] = 1 

for k in range(1,N+1):
    for s in range(1,N+1):
        if k==s:
            continue
        for g in range(1,N+1):
            if g==s:
                continue
            cnt = 0
            if arr[k][s] and arr[g][k]:
                cnt = 1

            arr[g][s] = max(arr[g][s], cnt)

answer = 0
for i in range(1,N+1):
    scnt = sum(arr[i])
    rcnt = sum([1 if arr[j][i] else 0 for j in range(1,N+1)])
    if scnt + rcnt == N-1:
        answer += 1

print(answer)

🎯 피드백 및 개선사항

처음에는 진입차수로 문제를 접근하려고 했고, 자기자신과 모두 연결되어있는 로직을 구하는과정이 까다로워 플로이드 워셜로 바꾸어 해결하였습니다.