[백준] 2458번 키 순서

💡문제접근

• 어떤 방법으로 플로이드-워셜 알고리즘을 적용해서 풀어야할지 고민을 많이 했다.

💡테스트케이스

입력
6 6
1 5
3 4
5 4
4 2
4 6
5 2

출력
1

• 위의 테스트케이스를 플로이드-워셜 알고리즘을 사용해 키의 관계를 2차원 리스트로 표현하면 다음과 같다.
  
• A → B의 관계로 표시할 수 있는데 편의상 A는 B보다 키가 작다고 하자.
• 4번의 경우 2번과 6번보다 작다는 것을 알 수 있다. (4, 2), (4, 6)
• 4번의 경우 1번과 3번, 5번보다 키가 크다는 것을 알 수 있다. (1, 4), (3, 4), (5, 4)
• 따라서, 각 번호별로 십자 모양으로 전부 확인하여 True의 값이 N-1이면 관계를 확인할 수 있다는 의미가 된다.

💡코드(메모리 : 117580KB, 시간 : 1372ms, PyPy3로 제출)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
graph = [[False] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().strip().split())
    # a가 b보다 키가 작다.
    graph[a][b] = True

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if graph[a][k] == True and graph[k][b] == True:
                graph[a][b] = True

answer = 0
for a in range(1, N+1):
    chk = 0
    for b in range(1, N+1):
        chk += graph[a][b] + graph[b][a]
    if chk == N-1:
        answer += 1
print(answer)

💡문제접근