(python) 그래프 순회 - 깊이 우선 탐색(DFS) (Feat. 백준 11403)

1. 깊이 우선 탐색(Depth-First Search)

 

깊이 우선 탐색 방식은 출발 정점으로부터 시작하여 연결된 정점을 거쳐

가장 멀리 있는 정점까지 방문하며 모든 정점을 방문하는 방식.

 

탐색하는 과정에서 더 이상 방문할 정점이 없는 경우에는

이전에 방문했던 정점으로 돌아가 미방문 정점을 확인한다.

 

DFS 예시

 

위의 그래픽은 실제 DFS 탐색의 과정을 보여준다.

 

2. 예제 적용(백준 11043)

 

백준 11403

 

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

11403번: 경로 찾기

 

문제 설명

 

방향 그래프에 대하여 각 정점으로 부터 방문할 수 있는 정점을 확인하여 출력

 

문제 풀이

 

1) 시작 정점으로부터 연결된 정점들 모두 탐색하며 정점 방문  (깊이우선탐색)

 

def dfs(s):   #방문할 정점이 없을 때 까지 재귀
    for i in range(n):
        if visited[i] == '0' and graph_list[s][i] == 1:
            visited[i] = '1'    #방문할 정점
            dfs(i)  #다음 정점에 대해 실행

 

전체코드

 

def dfs(s):   #방문할 정점이 없을 때 까지 재귀
    for i in range(n):
        if visited[i] == '0' and graph_list[s][i] == 1:
            visited[i] = '1'    #방문할 정점
            dfs(i)  #다음 정점에 대해 실행

n = int(input())
graph_list = []
for i in range(n):
    graph_list.append(list(map(int,input().split())))   #인접행렬 구성

for i in range(n):
    visited = ['0' for _ in range(n)]  # 정점 방문 초기화
    dfs(i)
    print(' '.join(visited))    #공백 포함한 문자열로 변환