[백준/파이썬] 11403번: 경로 찾기

문제

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

풀이

• 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로 탐색
• i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻
  • i번째 줄의 i번째 숫자는 항상 0

우선 저는 BFS로 풀었습니다.
각 정점마다 방문했는지 visited에 저장하고 연결이 되었다면 결과 배열에 1로 표시하였습니다.

def bfs(v):
    queue = deque([v]) # 시작 지점
    visited = [False] * n # 모든 정점마다 방문 여부를 확인해야 되므로 함수 내에 선언

    while queue:
        node = queue.popleft()
        for i in range(n):
            if graph[node][i] and not visited[i]: # 길이 있고 방문하지 않았다면
                visited[i] = True # 방문 표시
                res[v][i] = 1 # 경로 존재 표시
                queue.append(i)

코드

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

def bfs(v):
    queue = deque([v])
    visited = [False] * n

    while queue:
        node = queue.popleft()
        for i in range(n):
            if graph[node][i] and not visited[i]:
                visited[i] = True
                res[v][i] = 1
                queue.append(i)

if __name__ == "__main__":
    n = int(input())
    graph = [list(map(int,input().split())) for _ in range(n)]
    res = [[0] * n for _ in range(n)]

    for i in range(n):
        bfs(i)

    for r in res:
        print(*r)