[백준] 11403번, 경로 찾기 (Python)

문제

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

코드

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input())
demo = [list(map(int,input().split())) for _ in range(n)]
graph = [[INF for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        if demo[i][j] == 1:
            graph[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] == INF:
            print(0, end=' ') # 길이없는경우 INF일 경우에만 0을 출력
        else:
            print(1, end=' ') # 자기자신에게 가는것도 길이 있는것이므로 1이 출력된다.
    print()

모든 정점에 대하여 경로를 구하는 문제로 플로이드 와샬을 사용하여 풀었다.

 

플로이드 와샬은 3중 for문을 사용해 현재값과 k지점을 거쳐서 가는값중에 최소값을 저장합니다.

이 문제에서는 최단경로를 구하는 문제는 아니고 경로가 존재 하는지 아닌지를 찾는 문제이다.

 

graph에 값이 INF인 경우에만 경로가 접근할 수 있는 경로가 없으므로 0을 출력하고 나머지는 1을 출력한다.