BOJ - 2458

백준 문제 링크
키 순서

❓접근법

1. 플로이드 워셜 알고리즘을 활용했다.
2. 기본 플로이드 워셜 소스코드를 전개하는데,
   graph[a][b] > graph[a][k] + graph[k][b]이면
   graph[a][b] = 1로변환한다.
3. 2중 반복문으로 i, j를 움직여가며
   graph[i][j] == 1이면 cnt += 1 ( i -> j로 이동 가능 )
   graph[j][i] == 1이면 cnt += 1 ( j -> i로 이동 가능 )
   결과적으로 cnt == n - 1이면 answer += 1
4. 마지막으로 answer를 출력하면 끝 !

👌🏻코드

n, m = map(int, input().split())

INF = int(1e9)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if graph[a][b] > graph[a][k] + graph[k][b]:
                graph[a][b] = 1
                
answer = 0
for i in range(1, n + 1):
    cnt = 0
    for j in range(1, n + 1):
        if graph[i][j] == 1: # i 에서 j로 이동가능할 때
            cnt += 1
            
        if graph[j][i] == 1: # j 에서 i로 이동가능할 때
            cnt += 1
            
    if cnt == n-1:
        answer += 1
        
print(answer)