알고리즘 이론 - DFS

탐색

• 탐색이란 수많은 데이터에서 원하는 데이터를 찾는 과정임.
• 그래프 탐색 알고리즘에는 대표적으로 DFS, BFS가 있음.

DFS, BFS 전에 알아두면 좋은 것.(자세히는 나중에)

1.스택 -> 후입선출(LIFO) 마지막에 들어온 자료가 가장 나중에 나감

2. 큐 -> 선입선출(FIFO) 처음에 들어온 자료가 가장 빨리 나감.

3. 재귀 함수 -> 자기 자신을 다시 호출하는 함수.

• 팩토리얼, 유클리드 호제법(최대공약수) 등이 재귀에서 흔히 사용됨.
  -> 이는 나중에 따로 다룰 예정이다.

DFS

• DFS는 깊이 우선 탐색으로 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 스택 또는 재귀 함수를 이용한다.

순서

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면, 스택에 넣고 방문 처리. 모두 방문했다면, 최상단 노드를 pop함.

3. 2번 과정을 수행할 수 없을 때까지 반복.

위의 노드처럼 가장 작은 0 -> 1 순으로 방문하고 1과 인접한 3, 4중 3을 방문한다. 3은 더이상 방문할 수 없으므로 방문 처리 후 출력하고, 4를 방문한다. 그리고, 0을 제외하고 모두

# 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)
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
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)