[백준] 11403 - 경로 찾기 (플로이드 와셜)

JunHwa Park 2020. 10. 20. 13:24

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

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

n = int(input())
 
graph = [list(map(int, input().split())) for _ in range(n)]
 
for i in range(n):
    for a in range(n):
        if a == i:
            continue
        for b in range(n):
            if b == i:
                continue
            if graph[a][b] == 0 and graph[a][i] + graph[i][b] == 2:
                graph[a][b] = 1
 
for g in graph:
    for a in g:
        print(a, end=' ')
    print()
Colored by Color Scripter

cs

별거 없다. 그냥 플로이드 와셜 돌리면 된다.