[Graph]1403-パスの検索(52日目)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#정점의 개수 입력
N = int(input())

#정점 간 경로 가능 여부 저장 2차원 list 선언
answer = [[0 for _ in range(N)] for _ in range(N)]

#간선 저장을 위한 딕셔너리 선언 후 list로 초기화
#setdefault를 쓸 수 있으나 오히려 느려서 안씀
graph = {}
for i in range(N):
    graph[i] = []

#간선의 개수를 입력받고, 간선을 딕셔너리에 저장
for j in range(N):
    road = list(map(int, input().split()))
    for k in range(N):
        if(road[k] == 1):
            graph[j].append(k)

#출발 지점을 입력값으로 받는 DFS 탐색 함수
def DFS(root, graph):

    #출발 지점을 stack에 저장하고
    stack = [root]

    #탐색 지점이 남아 있는 동안 반복
    while stack:
        #탐색 지점을 추출하고
        index = stack.pop()

        #해당 탐색 지점과 연결된 모든 간선에 대해
        for value in graph[index]:
            #해당 도착점이 탐색된 적이 없을 시 경로 존재 체크 후 탐색 지점 추가
            if(answer[root][value] == 0):
                answer[root][value] = 1
                stack.append(value)

#1~N까지 출발지점으로 탐색하고
for i in range(N):
    DFS(i, graph)

#정답지 출력
for a in answer:
        print(*a)

#인사이트
#예제를 차분히 보며 문제를 이해했다면 빨리 풀 수 있었던 문제
#list 중심 그래프 풀이보다 느리긴 하지만, 간선 문제의 경우에는 딕셔너리 접근도 좋다
#각 정점에 대해 모두 탐색하기보다 적은 탐색으로 모든 가능성을 탐색할 수 있는 방법을 찾아야 함