[ 그래프 이론-11403 ] 경로 찾기(Python)

---

접근법

 

처음에는 배열 index가 다르기에 index를 맞추고자 입력받을 때 1인 경우만 graph 배열에 저장하여 dfs()를 돌 때, 1부터 N까지 각 노드에서 시작하여 끝까지 내려가는 경로 중 지나가는 노드를 따로 저장하여 다시 인접행렬로 출력하도록 구현하였다.

import sys
import heapq

sys.setrecursionlimit(10**6)

N = int(input())

graph = [[] for _ in range(N+1)]

resultGraph = [[0]* N for _ in range(N)]

def dfs(x,y,flag):
    
    if x == y and flag == False:
        flag = True
    elif x == y and flag == True:
        heapq.heappush(heap,y)
        return
    for k in graph[y]:
        heapq.heappush(heap,k)
        dfs(x,k,flag)
    
for i in range(N):
    tmp = list(map(int,sys.stdin.readline().split(" ")))
    for j in range(N):
        if tmp[j] == 1:
            graph[i+1].append(j+1)
            
for i in range(1,N+1):
    flag = False
    heap = []
    dfs(i,i,flag)
    if heap != []:
        while(heap != []):
            resultGraph[i-1][heapq.heappop(heap)-1] = 1
    
print(resultGraph)

 

하지만 메모리 에러가 나서 그냥 원초적인 방법으로 다시 접근하였다.

index에 집착하지 않고, dfs 방식으로 진행하되, 방문한 노드에 대한 배열을 매번 초기화 하고, 방문 정보를 할때마다 출력하도록 하면 쉽게 해결 가능하다.

또한, 입력받은 배열 자체를 활용하여 graph가 1이고 아직 방문하지 않은 노드에 대하여 dfs()를 적용하면 해결 가능하다.

---

정답

import sys
sys.setrecursionlimit(10**6)

N = int(input())

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

def dfs(x):
    for i in range(N):
        if graph[x][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            
for i in range(N):
    dfs(i)
    for j in range(N):
        if visited[j] == 1:
            print(1, end=' ')
        else:
            print(0, end=' ')
    print()
    visited = [0]* N

 

결국 가장 단순하게 접근하여 해결할 수 있었다..

이제는 dfs()와 bfs() 모두 사용하여 더 적은 메모리로 빠르게 해결할 수 있도록 연습할 필요가 있는 듯 하다..