[백준][Python] 2458 키순서

모든 노드에서 모든 노드까지의 정보를 구해야하는 플로이드 워셜 문제다.

요새 최단거리 문제해결 연습을 많이하고있는데

플로이드 워셜의 핵심은 이것.

"내가 저기 갈껀데 다른곳의 정보를 이용해서 가는게 빠르냐 아니면 그냥 가는게 빠르냐?"

이거다. 여기선 전자를 이용할 수 있느냐를 물어보는 문제.

(다른곳의 정보는 나뿐만아니라 도착지에서도 알고있어야한다.)

알고있다면 1 아니면 0

 

import sys
input = sys.stdin.readline

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

# 플로이드 워셜은 인접행렬을 쓴다.
for i in range(M):
    high, low = map(int, input().split())
    knowing_tall[high-1][low-1] =1

# 플로이드 워셜의 핵심은 matrix[a][b]랑 matrix[b][a]의 차이를 잘 생각하고 그래프를 설계.
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 내가 아는애랑 키차이 알고 걔가 다른애랑 키차이 알면 나도 걔랑 암.
            if knowing_tall[i][k] +knowing_tall[k][j]  ==2:
                knowing_tall[i][j] =1

know_cnt =[0 for _ in range(N)]
for i in range(N):
    for j in range(N):
        if knowing_tall[i][j] ==1:
            know_cnt[i] +=1
            know_cnt[j] +=1

print(know_cnt.count(N-1))