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

백준 - 11403 경로 찾기

풀이

한 점에서 다른 점까지 갈 수 있으면 1, 그렇지 않으면 0 출력 (행렬로)
-> 모든 점에서 dfs(bfs)를 하면 시간초과가 날 것 같았다.. 그래서 플로이드 워셜 알고리즘으로 풀이!

1. 맨 처음 값을 입력할 때 0이면 INF값으로 바꿔서 저장
   (자기 자신으로 가는 거리도 INF로 저장)
2. 플로이드 워셜로 최단 경로 구해줌
3. 그래프 순회하면서 저장된 값이 INF이면 0, 그렇지 않으면 1 출력

이 문제에서 예제를 볼 때 자기 자기 자신으로 가는 최단 경로를 무조건 0으로 두지 않았다
-> 다른 정점을 통해 자기 자신으로 갈 수 있는 지 계산해줌

코드

from sys import stdin
from sys import maxsize
from collections import deque

INF = maxsize
N = int(stdin.readline())
graph = []
visited = [0] * N

for i in range(N):
    input = list(map(int, stdin.readline().replace('0', str(INF)).split()))
    graph.append(input)

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 graph:
    for j in i:
        print(0, end=' ') if j == INF else print(1, end=' ')
    print()