백준 11403 경로 찾기 Python 3

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

11403번: 경로 찾기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ11403.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
sys.setrecursionlimit(10001)

def dfs(now, j):
    global visit
    for v, e in enumerate(graph[now]):
        if e and not visit[v]:
            visit[v] = 1
            dfs(v, j)

input = sys.stdin.readline
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

for i in range(N):
    line = ""
    for j in range(N):
        visit = [0] * N
        dfs(i, j)
        if visit[j]: line += "1 "
        else: line += "0 "
    print(line)

---

풀이 과정

풀이 시간 20분

import sys
#최대 100x100 그래프를 탐색해야하므로 재귀 한계를 늘려준다
sys.setrecursionlimit(10001)

def dfs(now, j):
    global visit
    #now 정점에 연결된 간선을 탐색한다
    for v, e in enumerate(graph[now]):
    	#간선이 있으면서 이전에 방문하지 않은 정점인 경우, 탐색을 이어나간다
        if e and not visit[v]:
            visit[v] = 1
            dfs(v, j)

input = sys.stdin.readline
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

for i in range(N):
    line = ""
    for j in range(N):
    	#i에서 j로 가는 경로가 있는지 탐색한다
        visit = [0] * N
        dfs(i, j)
        
        #경로가 있는 경우,
        if visit[j]: line += "1 "
        #경로가 없는 경우,
        else: line += "0 "
        
    print(line)
    
#시간복잡도 = O(N^2*(V+E)), 공간복잡도 = O(n)