[백준] 11403. 경로찾기 (bfs)

풀이1. BFS (시간 가장 빠름)

from collections import deque
def bfs(graph,start,visited): #bfs
    queue=deque([start])
    queue.append(start)
    while queue:
        v=queue.popleft()
        for i in range(n):
            if graph[v][i]==1 and not visited[i]:
                queue.append(i)
                visited[i]=True
                result[start][i]=1 #result[0][i]=1, result[1][i]=1...

n=int(input())
graph=[[0]*n for _ in range(n)]
result=[[0]*n for _ in range(n)] #정답 인접행렬
for i in range(n):
    graph[i]=list(map(int,input().split()))

for i in range(n):
    visited=[False]*n #매번 visited를 초기화해야함
    bfs(graph,i,visited) #bfs(0)~bfs(n-1)까지

for i in result: #인접행렬 출력
    print(*i)

 

풀이2. 플로이드-워셜 (생각만으로는 이렇게 못풀듯)

n=int(input())
graph=[[0]*n for _ in range(n)]
for i in range(n):
    graph[i]=list(map(int,input().split()))

for i in range(n):
    for j in range(n):
        for k in range(n):
            if graph[j][i]==1 and graph[i][k]==1:
                graph[j][k]=1

for i in range(n):
    print(*graph[i])