[DFS] 깊이탐색알고리즘(Depth-First Search)

DFS 란

Depth First Search 약자로 깊이 탐색 알고리즘을 말한다.

말그대로 깊이 있는 것부터 탐색을 한다는 것이다. 

이를 구현하기 위해선 스택이나 재귀함수를 이용한다. 

 

전제조건은 

노드를 방문하는 기준은 번호가 낮은 노드부터 방문한다고 하자.

우선 스택개념을 사용해서 DFS를 구현하자

1. 시작노드 : 1 

2. 1 방문 후 인접한 2, 3, 8 중 가장 가장 낮은 숫자를 스택에 넣는다. 

3. 2와 인접한 노드 중 방문하지 않은 7을 스택에 넣는다.

4. 7와 인접한 6과 8 중 가장 작은 6이 스택에 넣는다. 

5. 이제 6에서 더이상 들어갈 수 없기에 6을 꺼낸다.

6. 7와 인접한 6과 8 중 방문하지않은 8을 스택에 넣는다. (방문한다) 

7. 이제 8에서 더이상 들어갈 수 없기에 8을 꺼낸다.

8. 7과 인접한 모든 노드를 방문했기에 7도 꺼낸다.

9. 2도 꺼낸다

10. 1과 인접한 노드 중 방문하지 않는 3을 스택에 넣는다. 

 

탐색순서는 따라서 

 

1 -> 2 -> 7 -> 6 -> 8 ->3 -> 4 -> 5

 

이와 같은 논리로 스택의 변화과정을 본다면.

즉 정리하면,

 

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

2. 스택의 최상단 노드에 방문하지 않은 인접노드가 하나라도 있으면 방문하고, 

    인접한 노드를 모두 방문했다면, 스택의 최상단 노드를 꺼낸다. 

3. 2번과정을 수행할 수 없을때 까지 반복한다. (재귀함수로 해결가능. 종료조건이 포함되어있으니깐!) 

 

 

DFS 코드구현

# 각 노드가 연결된 정보를 표현 
# 0번노드는 없으니깐 빈리스트
# 1번노드에 연결된 노드는 2, 3, 8

graph = [
    [],
    [2, 3, 8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 노드 표현 
#>> 우선 모든 노드는 방문하지 않은 것처럼 
visited = [False] * 9
print(visited)

>>> [False, False, False, False, False, False, False, False, False]

# DFS 함수 구현
# 필요인자 : 그래프, 1번노드에서 출발, 방문리스트
def dfs(graph,v, visited):
    #현재 노드를 방문처리 
    #>>> 1번 노드 방문처리 
    visited[v] = True
    print(v, end= ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문! 
    # >>> 1번노드와 인접한 2,3,8 
    for i in graph[v]:
        # 인접한 노드가 방문하지 않는다면(True가 아니면) 즉, false면, 방문할 수 있도록
        # 2는 현재 False 2번노드에 대해 DFS 실행
        if not visited[i]:
            dfs(graph,i,visited)

 

여기서 헷갈렸던 코드구문은 

if not visited[i]이란 뜻으로 True가 아니면 이라는 뜻이다. 

a = False

if not a:
	print(a)
else:
	print('a는 True 입니다')

>>> False

 

참고문헌

이것이 취업을 위한 코딩테스트다 동영상을 공부하고 TIL입니다