티스토리 뷰

 경로의 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


결과는 1 --> 3 --> 4 --> 5> 2
결과는 stack 에 들어가는 순서에 따라서 바뀔 수 있다.


Test Code 


dfs.py


dfswithnode.py



Other Reference

  1. Depth-first  Search
    http://www.aistudy.com/heuristic/depth-first_search.htm
  2. Algorithm Tutorial : How To Find a Solution
    http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=findSolution
  3. http://code.activestate.com/recipes/576723-dfs-and-bfs-graph-traversal/


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함