백준
백준 11403 경로 찾기 (파이썬)
chldkato
2020. 2. 27. 16:14
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
from collections import deque
def bfs(x):
c = [0 for _ in range(n)]
while q:
nx = q.popleft()
for i in range(n):
if c[i] == 0 and a[nx][i] == 1:
c[i] = 1
m[x][i] = 1
q.append(i)
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
m = [[0]*n for _ in range(n)]
q = deque()
for i in range(n):
q.append(i)
bfs(i)
for i in m:
for j in i:
print("{0} ".format(j), end='')
print()