플로이드 워셜 알고리즘으로 해결하였다.
마지막에 inf 인 것들은 0으로 바꿔주고 나머지들은 모두 1로 바꿔주고 출력하였다.
import sys
from copy import deepcopy
from math import inf
n = int(input())
graph = [[inf]*n for _ in range(n)]
for i in range(n):
inn = list(map(int,sys.stdin.readline().split()))
for j in range(n):
if inn[j]:
graph[i][j] = 1
def floyd(graph):
d = deepcopy(graph)
for a in range(n):
for b in range(n):
for c in range(n):
d[b][c] = min(d[b][c], d[b][a] + d[a][c])
return d
d = floyd(graph)
for i in range(n):
for j in range(n):
if d[i][j]==inf:
d[i][j] = 0
else:
d[i][j] = 1
for i in range(n):
for j in range(n):
print(d[i][j],end =' ')
print()
'백준' 카테고리의 다른 글
Identify, Sort, Index, Solve - 26150번 (0) | 2022.12.04 |
---|---|
케빈 베이컨의 6단계 법칙 - 1389번 (0) | 2022.11.30 |
플로이드 - 11404번 (0) | 2022.11.29 |
듣보잡 - 1764번 (0) | 2022.11.14 |
좌표 정렬하기 2 - 11651번 (0) | 2022.11.08 |
댓글