11403 경로 찾기

www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

모든 지점에서 모든 경로에 대한 최소거리를 구하는 알고리즘은 플로이드 워셜 알고리즘이다.

 

O(N^3) 인 특징이 있으며 DP이다.

 

가장 중요한 부분인 3중 반복문 구문을 헷갈리면 안된다.

for i in range(n):
  for j in range(n):
    for k in range(n):
      if(graph[i][k]+graph[k][j] == 2 or graph[i][j] != 0):
        graph[i][j] = 1

for k in range(n):
  for i in range(n):
    for j in range(n):
      if(graph[i][k]+graph[k][j] == 2 or graph[i][j] != 0):
        graph[i][j] = 1

 

위 두 코드중 2번째 것이 플로이드 워셜 알고리즘이다. 거쳐가는 경로인 k가 최고 상위 반복문의 변수여야 한다.

이것을 헷갈려서 고민했던 문제였다.

 

import sys
input = sys.stdin.readline

n = int(input())
graph = []
answer = []
for _ in range(n):
  graph.append( list(map(int,input().rstrip().split(" ") )))

for k in range(n):
  for i in range(n):
    for j in range(n):
      if(graph[i][k]+graph[k][j] == 2 or graph[i][j] != 0):
        graph[i][j] = 1


for i in graph:
  print(" ".join( map(str,i) ))