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

티스토리 뷰

everything

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

koosal 2012. 7. 10. 02:10

경로의 cost 가 일정하고, 모든 곳을 방문할 필요가 있을 때 사용할 수 있다.

이 알고리즘은 shortest path(최단경로) 를 찾는 방법은 아니다.

tree 나 graph 를 탐색 하는데에 쓰이는 알고리즘이다. 다시 얘기하면, 자신의 data 가 tree 나 graph 의 모양이라면 쓸 수 있다.

예를 들면 트리로 되어 있는 알파벳들에서 특정 단어를 만드는 길, 다시 말하면, abc 는 트리에서 a를 거쳐, b를 거쳐 , c 에 도달하면 된다.는 식으로. 이때 가장 최적의 경로를 알려주지는 않는다.

어찌보면 그냥 tree 모양을 하고 있는 자료(data) 의 traverse(경로 탐색)을 하게 해주는 함수의 로직이라고 봐도 될 듯 하다.

그래서 조금 비틀어 생각해 보면, 모든 경우의 수를 따져보는 경우에 쓸모가 있을 수 있다.

그리고, 만약 원하는 목표 지점에 도달하는 동안에 대한 기록을 할 수 있기 때문에, 특정 경로에 이를 때까지 어디를 몇번 지나치는가, 등에 사용될 수 있다.

array 안에서 막혀있는 곳까지 색을 칠하거나, 너비를 구하거나 등의 array 안에서의 움직임을 응용해서 사용할 수 있다. 자세한 것은 ref. 2 의 flood fill 을 참고하자.

DFS(Depth First Search)

아래의 graph를 가지고 예를 들어보자.

adj[1] –> 2 –> 3
adj[2] –> 1 –> 4
adj[3] –> 1 –> 4
adj[4] –> 2 –> 3 –> 5
adj[5] –> 4

왼쪽은 stack 의 모습이고, 오른쪽은 operation 이다.


Empty_Stack	Top : 1 - mark 1 as visited - push 1’s neighbor nodes into the stack.
	- Pop
	Top : 3 - mark 3 as visited - push 3’s neighbor nodes into the stack.
	- Pop - Top : 1 --> but this is already visited. - Pop
	Top : 4 - mark 4 as visited - push 4’s neighbor nodes into the stack.
	- Pop
	Top : 5 - mark 5 as visited - push 5’s neighbor nodes into the stack.
	- Pop - Top : 4 --> but this is already visited. - Pop - Top : 3 --> but this is already visited. - Pop
	Top : 2 - mark 2 as visited - push 2’s neighbor nodes into the stack.
	- Pop - Top : 4 --> but this is already visited. - Pop - Top : 1 --> but this is already visited. - Pop. - Top : 2 --> but this is already visited. - Pop
Empty_Stack

이를 code로 나타내면 아래와 같다.

참고로 visited 를 체크하는 이유는 node 의 adjacent node 가 중복되어 들어가 있기 때문이다. 그렇지 않은 경우라면 굳이 visited 가 필요치 않다.

result = []
s = [];
dest = [1,3,4]
startNode.setVisited(True);
s.append(startNode);    # append() is the same as push()

while(len(s) != 0): # if the stack is not empty
    top = s.pop()   # see the first node & remove
    
    result.append(top.value); 
    if isIdentical(result, dest) : # check whether reached
            break   # success
            
    for v in adj[top.value]:    # if not, add the children node
        if v.visited is False:
            v.setVisited(True);
            s.append(v);

# print result
print result