[이코테] CH09 최단경로 실전문제 38번 정확한 순위

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9


N,M = map(int,sys.stdin.readline().split())
graph = [[INF] *(N+1) for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a][b] = 1 # 정순이면 a < b

for i in range(1,N+1):
    for j in range(1,N+1):
        if i == j:
            graph[i][j] = 0

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

count2 = 0
for i in range(1,N+1):
    count = 0
    for j in range(1,N+1):
        if graph[i][j]!=INF or graph[j][i]!= INF:
            count +=1
    if count == N:
        count2 +=1
print(count2)

플로이드 워셜 알고리즘이라고 생각할 수 있었던 힌트

1. 시간제한 5초

2. N이 500 이하까지만 허용 가능

 

처음엔 graph를 일차원으로 두는 다익스트라로 풀어야하나 싶었지만 시작점이 주어지지 않기도 했고

시작점이 주어지지 않는다면 다익스트라를 n회 돌려야 하는데 문제를 그렇게 내진 않겠지 싶었다

 

그래서 쉽게 플로이드 워셜 알고리즘으로 해결할 수 있었는데

기본 코드랑 좀 다른 점은 

graph[i][j]와 graph[j][i] 모두 고려해줘야 한다

왜냐면 graph[3][4]는 1이지만 graph[4][3]은 INF이므로

둘중 하나라도 INF가 아니라면 우선순위를 따질 수 있다는 이야기