[Python 3] 백준 11403-경로 찾기

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

11403번: 경로 찾기

우선적으로, 방문했음을 체크하는 2차원 배열 하나를 만든다.

그 이후, 모든 노드로부터 BFS를 실행하면서, 노드 하나를 방문할 때마다 배열에서 그 노드의 위치를 의미하는 위치의 값을 1로 수정한다.

모든 노드에 대해 BFS를 실행하면 결국 모든 노드를 다 방문하게 된다.

(deque 쓰면 속도 절감이 가능하다)

import sys
from collections import deque
INF=10**9

N=int(sys.stdin.readline())
graph={}
for i in range(N):
  graph[i]=[]
for i in range(N):
  adj=list(map(int, sys.stdin.readline().split()))
  for j in range(N):
    if adj[j]==1:
      graph[i].append(j)

def bfs(x):
  ret=[0 for i in range(N)]
  q=deque()
  q.append(x)
  while q:
    front=q.popleft()
    for i in graph[front]:
      if ret[i]==0:
        ret[i]=1
        q.append(i)
  return ret
  
for i in range(N):
  print(' '.join(map(str, bfs(i))))