[자료구조] 깊이우선탐색(DFS)

DFS란?

• Depth-Find Search로 깊이 우선 탐색 알고리즘
• 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘
• 그래프의 모든 Vertex와 Edge를 방문한다.
• Time Complexity는 O(n+m)
  => 모든 Vertex, Edge 통해 이동하고 노드와 인접한 노드가 visited인지 체크  * edge 개수에 비례
• 드라마로 예를 들었을 때, DFS는 한 드라마만 골라서 주구장창 본다고 하면, BFS는 여러 드라마를 한 번에 보는 느낌
• DFS에는 Back edge, BFS에는 Cross edge가 있다.
• DFS에선 Stack(또는 재귀함수) BFS에서는 Queue를 이용한다.

---

Properties of DFS

Property 1

    DFS(G, v)는 모든 Vertex, Edge를 v의 connected component 내에서 방문한다.

Property 2

    DFS(G, v)에서 형성된 discovery edge는 spanning tree Ts를 형성한다.

       +) spanning Tree : 모든 vertex를 지나는 tree의 subgraph

---

동작과정

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

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.

    방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

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

---

Analysis of DFS

• vertex/edge label을 Setting/getting 하는데 O(1) time이 걸린다. (여기서 label은 상태 ex) visited, discovery, cross )
• 각 vertex는 2번 label이 지정된다.(UNEXPLORED / VISITED)
• 각 edge는 2번 label이 지정된다. (UNEXPLORED /  DISCOVERY or BACK)
• Method incidentEdges는 각 vertex에서 한 번 호출된다.
• n = 정점 수(vertex), m = 간선 수(edge)일 때, 그래프가 Adjacency List structure로 표현될 경우 O(n+m)
• n = 정점 수(vertex)일 때, 그래프가 Adjacency Matrix로 표현될 경우 O(n^2)

---

PseudoCode

1) Path Finding

Algorithm pathDFS(G,v,z):
	setLabel(v, VISITED)
    S.push(v)
    if v == z
    	return S.elements()
    for all e in G.incidentEdges(v)
    	if getLabel(e) = UNEXPLORED
        	w = opposite(v, e)
            if getLabel(w) = UNEXPLORED
            	setLabel(e, DISCOVERY)
                S.push(e)
                pathDFS(G,w,z)
                S.pop(e)
            else  // 이미 방문
            	setLabel(e, BACK)
    S.pop(v)

 

2) Cycle Finding

Algorithm cycleDFS(G,v,z):
	setLabel(v, VISITED)
    S.push(v)
    for all e in G.incidentEdges(v)
    	if getLabel(e) = UNEXPLORED
        	w = opposite(v,e)
            S.push(e)
            if getLabel(w) = UNEXPLORED
            	setLabel(e, DISCOVERY)
                cycleDFS(G,w,z)
                S.pop(e)
            else
                T = new empty stack
                while o != w
                	o = S.pop()
                    T.push(o)
                return T.elements()
         S.pop(v)

---

Python Implementation

def DFS(g,u,discovered): # Graph g, starting at Vertex u
	for e in g.incident_edges(u):
    	v = e.opposite(u)
        if v not in discovered:
        discovered[v] = e
        DFS(g,v,discovered)

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [], # 0번째는 비우기
    [2, 3, 8], # 1번 노드랑 연결된 노드
    [1, 7], # 2번 노드랑 연결된 노드
    [1, 4, 5], # 3번 노드랑 연결된 노드
    [3, 5], # 4번 노드랑 연결된 노드
    [3, 4], # 5번 노드랑 연결된 노드
    [7], # 6번 노드랑 연결된 노드
    [2, 6, 8], # 7번 노드랑 연결된 노드
    [1, 7] # 8번 노드랑 연결된 노드
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

C++ Implementation

#include <iostream>
#include <utility>
#include <stack>
using namespace std;

#define X first
#define Y second

int board[502][502] = { // 1이 blue, 0이 red
 {1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} };
bool vis[502][502];
int n = 7, m = 10;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
	stack<pair<int, int> > S;
	vis[0][0] = 1;
	S.push({ 0, 0 });

	while (!S.empty()) {
		pair<int, int> cur = S.top();
		S.pop();
		cout << '(' << cur.X << ", " << cur.Y << ") ->";
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (vis[nx][ny] || board[nx][ny] != 1)
				continue;
			vis[nx][ny] = 1;
			S.push({ nx,ny });
		}
	}
}

 

---

Q : DFS는 Shortest paths를 찾는데 왜 자주 쓰이지 않을까?

A : DFS로 경로를 검색할 경우 처음으로 발견한 경로가 최단거리가 아닐 수 있다. 만약, 트리라는 확신이 있다면 노드간 경로가 하나만 존재하기 때문에 최단경로일 수 밖에 없다. 반면에 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로 탐색시 먼저 찾아지는 경로가 최단 경로이다.

 

 

---

참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬, 바킹독 알고리즘