Depth-First Search(DFS)

특징

• 깊이 우선 탐색: 깊은 부분을 우선적으로 탐색
• 스택 자료구조나 재귀함수를 이용

• 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려 시도
• 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다

DFS 동작 예시 및 파이썬 소스코드

def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드 재귀적으로 방문
    for i in graph[v]"
    	if not visited[i]:
        	dfs(graph, i, visited)
            
    # 각 노드(1~8)가 연결된 정보 표원(2차원 리스트)
    graph = [
    	[],       # 문제가 1번 노드부터 시작하는 경우가 많아 0번 인덱스 비워두고 시작
        [2, 3, 8]
        [1, 7]
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]
    ]

	# 각 노드가 방문된 정보를 표현(1차원 리스트)
    visited = [False] * 9   # 초기값으로 False를 줌으로써 시작할 시 모든 노드를 방문하지 않은 것으로 처리.
    			    # 여기서 9는 1번~8번 노드 + 빈 인덱스 [0]까지 포함
    
    # 정의된 DFS 함수 호출
    dfs(graph, 1, visited)

References

• 동빈나, 이코테 2021 강의 몰아보기 3.DFS & BFS, https://www.youtube.com/watch?v=7C9RgOcvkvo&list=LL&index=1&t=966s
• 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략