[백준] 11403 - 경로 찾기 [Python(파이썬)]

문제

www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

풀이

정점을 탐색하는 건 어렵지 않지만, 경로를 기록하는 것이 까다롭다.

이차원 리스트에 경로를 저장하면 수월하게 해결할 수 있다.

 

DFS/BFS 탐색 시 탐색을 시작하는 정점(start)을 매개변수로 넘겨주고 방문하는 정점마다 경로에 추가하면 된다.

즉, 현재 정점(cur)을 방문하면 path[start][cur] = 1이 된다.

이때 탐색하는 과정에서 사이클이 존재하는지 여부를 확인해줘야 한다.

 

코드

import sys
sys.setrecursionlimit(10**6)

def dfs(start, cur):
    visited[cur] = 1
    
    if start != cur:
        path[start][cur] = 1

    for u in range(n):
        if u != cur and g[cur][u] and not visited[u]:
            dfs(start, u)
        if u == start and g[cur][u]: # 사이클이 존재하는지 확인한다.
            path[start][start] = 1


n = int(sys.stdin.readline().strip())
g = []
path = [[0 for _ in range(n)] for _ in range(n)]

for _ in range(n):
    raw = [int(x) for x in sys.stdin.readline().split()]
    g.append(raw)

for i in range(n):
    visited = [0 for _ in range(n)]
    dfs(i, i)            

for raw in path:
    print(*raw)