BOJ 11403번: 경로 찾기

www.acmicpc.net/problem/11403

11403번: 경로 찾기

아이디어:

플로이드 와샬 알고리즘을 이용하여 경로를 찾고, 경로가 있는 경우와 없는 경우만 구별해서 출력하면 된다.

graph로 입력받은 배열에서 경로가 존재하지 않는 경우(0인 경우)에 0 대신 INF값을 넣었고, 이를 이용하여 플로이드 와셜 알고리즘으로 탐색하였다. 그 후, graph[i][j]==INF면 0을, 아니면 1을 출력하였다.

 

import sys

N = int(sys.stdin.readline())
graph = [[] for _ in range(N)]
for i in range(N):
    graph[i] = list(map(int, sys.stdin.readline().split()))
INF = 10**9
for i in range(N):
    for j in range(N):
        if (graph[i][j]==0):
            graph[i][j]=INF
            
dist = [[INF]*N for _ in range(N)]
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=" ")
        else:
            print(1, end=" ")
    print()