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

1ㄷ1 관계는 선형구조라고 불렀고 1ㄷN의 관계는 트리라고 불렀다.

그럼 N:N의 관계는 어떤 구조일까? 바로 그래프 구조라고 부른다. 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다.

특히, 그래프와 비슷한 트리와의 큰 차이점은, 순환(Cycle) 할 수 있다는 것

 

이를 위한 탐색 방법 2가지가 있는데 오늘은 우선 DFS에 대해 알아볼 것이다.

• 깊이 우선 탐색 (Depth First Search, DFS)
• 너비 우선 탐색 (Breadth First Search, BFS)

두 방법의 차이

• DFS는 탐색을 한 뒤 이전의 정점으로 돌아온다
• 이것은 백트래킹(Backtracking)이라고 부른다

 

# DFS - 깊이 우선 탐색

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,  가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입 선출 구조의 스택 사용

과정

1. 시작 정점 v를 결정하여 방문
2. 정점 v에 인접한 정점 중에서
   1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 정점 w를 방문한다. 그리고 w를 v로 하여금 다시 2)를 반복한다.
   2. 반복하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop 하여 받은 가장 마지막 방문 정점을 v로 하여 다시 2)를 반복한다.
3. 스택이 공백이 될 때까지 2)를 반복한다.

visited[], stack[] 초기화
DFS(v)
	시작점 v 방문;
    visited[v] <- true;
    while {
    	if ( v의 인접 정점 중 방문 안 한 정점 w가 있으면)
        	push(v);
            v <- w; (w에 방문)
            visited[w] <- true;
        else
        	if (스택이 비어 있지 않으면)
            	v <- pop(stack);
            else
            	break
                
      }
  end DFS()

 

그림을 보며 더 쉽게 이해해보자.

1. a 노드(시작 노드)를 방문한다.
   • 방문한 노드는 방문했다고 표시한다.
2. a와 인접한 노드들을 차례로 순회한다.
   • a와 인접한 노드가 없다면 종료한다.
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
   • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
   • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻
   • 아직 방문이 안 된 정점이 없으면 종료한다.
   • 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

구현 방법

스택 또는 재귀 방식을 이용하여 구현할 수 있다. 

• 스택은 FILO(First-In, Last-Out) 방식이기 때문에 인접한 정점이 우선이 아닌 더 멀리 있는(인접 정점의 끝) 정점을 우선 탐색한 뒤 돌아올 수 있다. 큐는 FIFO라서 인접 정점을 우선하여 탐색하므로 쓸 수 없다. 큐는 BFS에 사용
• 재귀 방식으로 진행하는 것 또한 가능하다. 재귀 자체가 내부적으로 Stack을 사용하는 방식이기 때문이다. 둘 중에선 재귀 방식이 더 많이 쓰인다. 더욱 구현이 간단하기 때문이다.

시간 복잡도 : O(V+E), V는 정점 / E는 간선의 개수로 그 개수에 따라 전체 탐색에 시간이 소요된다.(인접 행렬은 O(V^2))

# 스택이용 구현

# 시작하는 정점 정보 전달 받아서
def DFS(start):
    # 다음 조사 위치 쌓아 나가기 위해서
    stack = [start]
    # 한번 방문헀던 곳 재 방문 하지 않도록 하기위한
    # 방문 가능한 크기 만큼
    # 기본적으로 방문 안헀음이 default 이므로 0으로 초기화
    visited = [0] * (V+1)

    # 전수 조사 시작 할건데
    # 언제까지 조사 할 것이냐
    # stack이 빌 때까지
    while stack:
        # 내 조사 대상 == stack의 마지막 정점
        start = stack.pop()

        # 해당 정점이 아직 방문하기 전
        if visited[start] == 0:
            # 일단 방문
            visited[start] = 1
            print(start, visited)

            # 모든 정점들 조사
            for next in range(1, V+1):
                # start 번째 기준으로 next가 이동 가능하고
                # next 번째가 방문 하기 전이라면
                if G[start][next] == 1 and  visited[next] == 0:
                    # stack에 next 정점 추가
                    stack.append(next)
                    print(stack)

 

 

# 재귀이용 구현

def DFS(start):
    visited[start] = 1
    print(start, visited)

    for next in range(1, V+1):
        if G[start][next] == 1 and visited[next] == 0:
            DFS(next)

 

응용

1. 최단 경로 찾기 및 최소 스패닝 트리
2. 순환 탐지
3. 위상 정렬
4. Puzzle 풀이 (하나의 solution) 찾기

이 외에도 굉장히 많이 사용된다. 아직 필요한 자료구조에 대해서도 많이 공부하지 못하여 간단하게만 알아보았다.

다음에 자료구조를 더 열심히 공부한 이후에 자세하게 알아보자!