[파이썬] 문제 : dfs 코드 해석

파이썬 코드해석

DFS는 깊이우선탐색이라고 합니다.

결과를 보면 0, 2, 3, 8 과 같이 세로축으로 쭉 내려가면서 검색합니다.

이를 구현한 코드 입니다.

함수가 자기자신을 실행하는 재귀함수를 사용해서 구현 합니다.

adj_list = [[2, 1],  [3, 0], [3, 0], [9, 8, 2, 1],       # 위 그림을 보면 0번은 2, 1번과 연결괴어 있습니다. 인덱스 0번이 2,1번 연결 표시
           [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]     # 그러한 연결을 리스트로 만든 것임

n = len(adj_list)                         # 10. adj_list의 요소 갯수
visited = [False for _ in range(n+1)]   # visited = [False, False...False]. 10개의 False기 있는 리스트

def dfs(v):                 # DFS (Depth first search) : 깊이우선 탐색
    visited[v] = True        # 방문했다고 표시
    print(v, ' ', end='')     # 출력. 방문 순서를 출력
    for w in adj_list[v]:    # adj_list의 u 인덱스 요소. 즉 [2,1] 또는 [3,0]과 같이 됨
        if not visited[w]:   # visited[w]가 False 면 이라는 뜻. 즉 방문하지 않았으면이 됨.
            dfs(w)            # 재귀함수 즉 자기자신을 실행. 이때 인자를 넘겨 줌
            
print('DFS 방문 순서:')
for i in range(n):
    if not visited[i]:
        dfs(i)

결과