BOJ 11403 경로 찾기

https://www.acmicpc.net/problem/11403
시간 2초, 메모리 128MB
input :

• N (1 ≤ N ≤ 100)
• 인접 행렬 (숫자가 1 간선이 존재, 0인 경우는 없다는 뜻)

output :

• N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식

---

모든 노드들에 대해서 bfs를 수행해야 한다. 양방향 그래프 이기 때문에 cycle이 되어서 자기자신으로 올 수도 있기 때문에 이를 생각해서 visit을 업데이트 해주어야 한다.

import sys
from _collections import deque

n = int(sys.stdin.readline())
graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

def bfs(start):
    q = deque([start])

    while q:
        now = q.popleft()
        for i in range(n):
            if graph[now][i] == 1 and visit[i] == 0:
                q.append(i)
                visit[i] = 1
                graph[start][i] = 1

for i in range(n):
    visit = [0] * n
    bfs(i)

for i in range(n):
    for j in range(n):
        print(graph[i][j], end=" ")
    print()