[알고리즘] DFS(깊이우선탐색)

당고짱·2022년 4월 15일
0

Algorithm

목록 보기
8/8
post-thumbnail

🧐 DFS란?

  • Depth First Search
  • 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘
  • 준비물 : Stack(LIFO)
  • 스택을 사용하지 않아도 구현이 가능 (컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문)

🎈 DFS 방법

DFS는 아래와 같은 간단한 알고리즘에 따라 작동한다.

  1. 스택의 최상단 노드를 확인한다.
  2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.



맨 처음 시작 노드를 스택에 삽입하면서 시작한다.(빨간색으로 표시한 노드는 방문한 노드)


스택에 있던 최상단 노드가 (1)이므로 인접한 노드 중에서 방문하지 않은 (2)노드를 넣는다.


이후, 노드(2)의 인접 노드 중 방문하지 않은 노드(3)을 스택에 넣는다.


노드(3)의 인접 노드 중, 방문하지 않은 노드(6)을 스택에 넣는다.


노드(6)의 인접 노드 중, 방문하지 않은 노드(7)이 스택에 삽입된다.


노드(7), (6), (3)은 인접 노드를 전부 방문했기 때문에 스택에서 빠져나온다. 이후 노드(2)를 보았을 때, 인접 노드(4)를 방문하지 않았으므로 노드(4)를 스택에 넣는다.


노드(4)의 인접 노드(5)가 스택에 들어간다.이후 스택에서 하나씩 노드들이 빠져나온다.


따라서 방문 경로는 1-2-3-6-7-4-5가 된다.

🎈 DFS 코드 (파이썬)

# 방향이 있는 유향그래프
graph_list = {1: set([3, 4]),
	2: set([3, 4, 5]),
    3: set([1, 5]),
    4: set([1]),
    5: set([2, 6]),
    6: set([3, 5])}
    
 
root_node = 1
# DFS
def DFS_with_adj_list(graph, root):
	visited = []
    stack = [root]
    
    while stack:
    	n = stack.pop()
        if n not in visited:
        	visited.append(n)
            stack += graph[n]-set(visited)
    return visited
print(DFS_with_adj_list, root_node))

위 내용은 https://blog.naver.com/ndb796/221230944971 를 참고하여 작성되었습니다.
이미지 참고 : Wikimedia Commons

profile
초심 잃지 말기 🙂

0개의 댓글