[DFS, 파이썬] 백준 11403. 경로찾기

 

경로 찾는 문제, 방향이 있는 그래프 문제이다.

DFS 선언 내부 for 문은 매개변수 v행 에 호응하는 열i 에 해당한다. 행 단위로 확인하기 때문에 visit이 2차원이 아니다. 또 visit을 반복문 내에서 출력하는 게 다른 DFS와의 차이점이다. 간단하지만 아직 연습이 더 필요한 문제이다.

 

 

import sys
sys.stdin = open('graph input.txt', 'rt')
input = sys.stdin.readline

size = int(input())
visit = [0 for i in range(size)]
g = [list(map(int, input().split())) for _ in range(size)]

def DFS(v):
    for i in range(size):
        if visit[i] == 0 and g[v][i] == 1:
            visit[i] =1
            DFS(i)

# DFS 호출, visit 초기화
for i in range(size):
    DFS(i)
    for j in range(size):
        if visit[j] == 1:
            print(1, end = ' ')
        else:
            print(0, end=' ')
    print()
    visit = [0 for i in range(size)]

 

 

참고

https://pacific-ocean.tistory.com/261