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

 

DFS (Depth First Search)

---

그래프를 전체 탐색하는 깊이 우선 탐색 DFS는 탐색을 시작한 시작점부터 해당 부분을 완벽하게 탐색하고 다음으로 넘어가는 방식이다. 아래 그림을 보면 좀더 빠르게 이해할 수 있다.

위 그림처럼 한개의 분기에 대해 모든 탐색이 완료되면 다음 분기로 넘어가고, 완벽하게 탐색한 후에 다음 분기로 넘어가는 흐름을 띄고 있다. 이는 스택, 재귀호출 방식으로 구현할 수 있다. 일반적으로 재귀호출을 사용하였을때 구현하기 편해 자주 사용하지만, 스택오버플로우가 발생할 수 있기 때문에 잘 구현해야 한다 (노드 방문시 방문여부를 검사하면서 진행해야 무한반복에 빠지지 않을 수 있다).

 

 

장점

---

한 분기의 깊이가 깊더라도 완벽하게 탐색하고 다음 분기로 넘어가기 때문에 목표노드가 깊은 단계에 있을 경우 다른 알고리즘보다 빠르게 원하는 값을 찾을 수 있다. 또한 저장공간을 비교적 적게 차지한다.

 

 

 

단점

---

한 분기를 완벽하게 탐색하고 다음 분기로 넘어가는 특성이 단점으로도 작용할 수 있는데, 탐색하는 분기에 원하는 값이 없는 경우라도 완벽하게 탐색한 후 다음 분기로 이동하기 때문에 해가 없는 경로에서 깊게 빠질 수 있다. 이러한 문제는 깊이를 제한하여 제한 깊이 안에 원하는 값이 존재하지 않으면 다음 분기로 넘어가도록 구현하여 해결할 수 있다.

또한 얻어진 해가 최단 경로가 아닐 수 있다. 

 

 

구현 방법

---

DFS는 여러가지 방법으로 구현할 수 있다. 스택/큐를 이용해서 구현할 수 도 있고, 덱을 이용해서 구현하기도 한다. 또한 재귀함수로 구현할 수 도 있다. 필자는 재귀함수로 구현하는게 가장 편하지 않나 싶다. 구현에 대한 예제소스는 하단 레퍼런스엥 걸려있는 블로그를 참고하였다 (감사합니다).

위와 같은 그래프가 존재한다고 가정해보도록 하겠다. A부터 K까지의 노드로 연결되어있고 방향성은 존재하지 않는다. DFS는 한 분기에 대해서 말단노드까지 탐색하고 다음분기로 넘어간다. 이제 재귀호출 방식으로 탐색을 진행해보겠다.

# 파라미터
# graph: 그래프가 정의되어있는 딕셔너리 (혹은 리스트일 수도 있고)
# start: 시작 노드
# visited: 방문한 노드 (DFS에서는 필수로 방문하였던 노드를 기억하고 있어야 한다)

def dfs_recursive(graph, start, visited = []):
    # visited list에 시작 노드를 추가
    visited.append(start)
    # 시작 노드와 연결되어있는 노드를 하나씩 방문하면서
    for node in graph[start]:
        # 만약 해당 노드가 한번도 방문하지 않은 노드라 하면
        if node not in visited:
            # 재귀호출을 통해서 노드의 방문을 진행한다.
            dfs_recursive(graph, node, visited)
    return visited

재귀호출 방식으로는 위와 같이 구현할 수 있다. DFS에서는 필수로 방문하였던 노드를 기억하고 있어야 하기 때문에 visited라는 리스트를 할당에서 방문하였는지, 방문한 적이 없는지를 확인한다.

 

덱을 이용하여 DFS를 구현할 수도 있다. 동작하는 방식은 거의 유사하다. 노드 방문 -> 방문한 노드 기억 -> 기억을 바탕으로 방문하지 않은 노드라면 다시 방문, 방문한 노드라면 패스

from collections import deque

# 파라미터
# graph: 그래프가 정의되어있는 딕셔너리
# start_node: 시작 노드
def dfs_deque(graph, start_node):
    # 방문 여부를 기억하고 있는 리스트 할당
    visited = []
    # 방문이 필요한 노들을 관리하는 덱 할당
    need_visited = deque()
    # 방문이 필요한 노드를 관리하는 덱에 시작 노드 삽입
    need_visited.append(start_node)
    
    # 반복문을 통해서 방문이 필요한 노드들을 확인
    while need_visited:
        # 가장 앞에 있는 노드를 추출
        node = need_visited.popleft()
        # 이 노들을 방문한 적이 없다면
        if node not in visited:
            # 방문을 하고 방문 여부를 확인하는 리스트에 노드 추가
            visited.append(node)
            # 이 노드와 연결되어있는 노드들을 덱에 삽입
            need_visited.extend(graph[node])
                
    return visited

 

 

 

 

 

예시

---

DFS는 여러가지 방법으로 구현할 수 있다. 스택/큐를 이용해서 구현할 수 도 있고, 덱을 이용해서 구현하기도 한다. 또한 재귀함수로 구현할 수 도 있다. 필자는 재귀함수로 구현하는게 가장 편하지 않나 싶다.

DFS 문제를 많이 풀어본건 아니지만 그래프가 다음과 같이 주어지는 상황이 있기도 하다. 

참고로 이 문제는 백준의 2606 바이러스 문제이다. 위와 같이 문제가 주어지고 예제 입력으로는 다음과 같이 주어진다.

이때 세번째줄부터 마지막줄까지 노드들의 연결성을 나타내고 있다. 위를 통해서 그래프를 만들어주면 된다. 이번 문제의 경우는 방향성이 존재하지 않기 때문에 1번에서 연결되어있는 애들 모두, 2번에서 연결되어있는 모든 노드를 리스트로 표현해줄 것이다.

위사진과 같이 graph리스트를 만들고 이걸로 그래프를 표현하였다. 리스트의 인덱스번호를 컴퓨터 번호로 생각하면 되고, 요소 안의 리스트는 연결되어있는 노드들을 나타낸다고 생각하면 된다. 반복문을 통해 graph 리스트를 채운다. 여기서 컴퓨터는 1번부터 시작하기 때문에 이해를 쉽게 하기 위해서 0번인덱스는 사용하지 않고 1번 인덱스부터 사용하였다. 

그래프를 다 생성하였다면 이제 재귀호출 방식을 이용해서 노드들을 탐색하면 된다.

위에서 확인할수 있는 것 처럼 재귀함수에서 방문하였는지 방문하지 않았는지에 대한 여부를 체크하면서 재귀호출방식으로 노드들을 방문하고 방문을 성공하면 count+=1 씩 취하고 있다. 그렇기 때문에 총 몇대의 컴퓨터가 바이러스에 감염되어있는지 확인할 수 있다. 여기서는 방문하였는지 방문하지 않았는지를 리스트로 확인하는데 처음에 컴퓨터 개수만큼 리스트를 생성하고 0으로 초기화시킨 다음에 방문한 논드는 1로 표시를 하여 관리하였다.

 

 

 

Reference

---

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

https://data-marketing-bk.tistory.com/44

DFS 완벽 구현하기 - 파이썬