📌 [BOJ] 백준 11403 경로 찾기

문제

예제

풀이

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())

graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

def BFS(x):
  queue = deque()
  queue.append(x)
  check = [False] * N
  while queue:
    q = queue.popleft()
    for i in range(N):
      if not check[i] and graph[q][i] == 1:
        check[i] = True
        queue.append(i)
        visited[x][i] = 1
        
for i in range(N):
  BFS(i)
for i in visited:
  print(*i)

BFS를 이용하여 문제를 해결할 수 있다.
다른 문제들과 다른 점은 각 노드에 대해 BFS를 모두 적용해가며 연결된 노드들을 탐색한다는 것이다.