[Python] DFS(Depth First Search) 알고리즘

*해당 포스팅은 이것이 코딩 테스트다 with python(나동빈 지음) 교재를 공부하며 작성한 글입니다.

 

 

 

안녕하세요! 오늘은 DFS 알고리즘에 대해 알아보겠습니다.

 

DFS란 'Depth First Search'의 약자로 깊이 우선 탐색이라고 불리며, 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘입니다.

 

DFS 알고리즘은 주로 경우의 수에 대해 알고 싶을 때 사용합니다.

 

DFS 알고리즘을 이해하기 위해서는 먼저 스택 구조와 그래프의 구조에 대해 알아야 합니다.

 

1. 스택 (Stack)

 

스택은 선입 후출(First In Last Out)의 구조입니다. 스택은 박스 쌓기에 비유해 볼 수 있습니다.

 

박스를 아래에서 위로 차곡차곡 쌓은 후에 박스를 치우기 위해서는 위에서부터 치워야 합니다. 

 

그림으로 보면 다음과 같습니다.

 

 

스택 구조

 

 

파이썬에서는 스택에 데이터를 삽입할 때 stack.append() 를 사용하고 삭제할 때는 stack.pop() 를 사용합니다. 

 

*재귀 함수가 내부적으로 스택 자료구조와 동일하다는 것을 알아두면 DFS 알고리즘을 이해하는데 도움이 됩니다.

 

2. 그래프

 

그래프는 노드와 간선으로 표현되고 이때 노드를 정점이라고도 말합니다.

 

그래프 탐색이란 하나의 노드에서 시작하여 다른 다수의 노드를 방문하는 것을 말합니다.

 

그래프는 크게 2가지 방식으로 표현할 수 있습니다.

 

 

① 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

 

 

[좌] 그래프    [우] 그래프를 인접 행렬로 표현

 

 

② 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

 

 

그래프를 인접 리스트로 표현

 

 

이 두 방식에는 어떤 차이가 있을까요?

 

메모리 측면에서 살펴보면 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비되게 됩니다.

 

하지만 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있습니다.

 

따라서, 특정 노드와 연결된 모든 노드를 순회해야 하는 경우 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다고 볼 수 있습니다. 

 

 

이제 DFS 알고리즘에 필요한 스택 구조와 그래프의 기본 구조에 대해 알아보았으니 DFS 알고리즘에 대해 자세히 알아보도록 하겠습니다.

 

DFS의 동작 과정은 다음과 같습니다.

 

 

① 탐색을 시작할 노드를 스택에 삽입하고 방문 처리를 한다.

 

② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 인접 노드가 모두 방문 처리되어있을 경우에는 스택에서 다음 최상단 노드를 꺼낸다.

 

③  2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

코드로 이 과정을 알아보겠습니다.

 

 

visited=[False]*9

def dfs(graph,v,visited):
  #현재 노드 방문 처리
  visited[v]=[True]
  print(v, end=' ')
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

 

 

코드를 보면 visited 리스트는 방문처리를 할 리스트를 뜻합니다.

 

graph는 자신이 원하는 대로 2차원 리스트 자료형으로 입력하면 됩니다.

 

반복문을 보면 최상단 노드(v)의 인접 노드(i) 중에서 방문하지 않은 노드가 있다면

 

그 노드를 재귀적으로 방문하여 가장 깊숙한 곳까지 방문하였다가 다시 돌아와 다른 방향으로 깊숙이 방문하게 됨을 알 수 있습니다.

 

코드를 봤을 때 '어떻게 다시 돌아오는가'가 저는 처음에 이해가 가지 않았는데

 

위에 스택 구조에 대해 설명할 때 재귀 함수가 내부적으로 스택 구조와 동일하다고 말씀드린 것을 생각하면 이해하기 편하실 것이라 생각합니다.

 

 

만약 그래프에서 제일 깊숙이 있는 최하단 노드(v)의 인접 노드(i)가 모두 방문되었다면

 

스택에서 꺼내고 스택의 다음 최상단 노드가 새로운 기준(v)이 되어 다시 인접 노드(i)의 방문 여부를 확인합니다.

 

이 과정을 반복하면 결국 위로 다시 돌아가서 다른 방향의 탐색하지 않은 노드를 탐색할 수 있습니다.

 

말로 설명해서 이해가 잘 안 가실 수도 있는데 그래프와 스택을 그려서 한 단계 한 단계 직접 해보시면 완벽히 이해가 가실거라 생각합니다.

 

 

 

지금까지 DFS 알고리즘의 원리에 대해 알아보았습니다.