2023.01.25 경로찾기 백준[파이썬]

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

11403번: 경로 찾기

 

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

def dfs(v):
    visited = []
    discovered = [v]
    while discovered:
        pos = discovered.pop()
        visited.append(pos)
        for i in graph_dict[pos]:
            graph[v][i] = 1
            if i in discovered or i in visited:
                continue
            discovered.append(i)

N = int(input().strip())

graph  = [list(input().split()) for _ in range(N)]
graph_dict = defaultdict(list)
for i in range(N):
    for j in range(N):
        if graph[i][j] == '1':
            graph_dict[i].append(j) 

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

for i in graph_dict.copy().keys(): 
    dfs(i)

for i in graph:
    print(*i)

dfs를 사용해서 구했다. dfs를 돌릴때 다른 오류가 떠서 copy를 해줬다. 아마 iterate 값이 달라져서 오류가 발생한거 같다.

문제를 푸는데 지금 너무 정형화된 dfs 모양을 사용하는지 걱정이 된다. 다른 방법으로 생각이 안 펴져서 조금 더 쉬운 방법이 있을 수 있다고 생각하지만... 이 부분에 대해서는 조금 더 고민을 해봐야겠다.