(Python) 깊이 우선 탐색(DFS) 구현하기

깊이 우선 탐색(DFS) 구현하기¶

---

In [1]:

graph = {'A':['B','C'],
         'B':['A','D','E'],
         'C':['A','G','H'],
         'D':['B'],
         'E':['B','F'],
         'F':['E'],
         'G':['C'],
         'H':['C']}

반복문(iteration)을 이용해서 DFS 구현하기¶

dfs는 stack을 이용해서, bfs는 queue를 이용해서 구현할 수 있는데
이는 다른 블로그에서도 쉽게 설명해 놓은 것이 많으니 개념을 모른다면 참고하자.

---

In [2]:

def dfs_iteration(graph, root):
    # visited = 방문한 꼭지점들을 기록한 리스트
    visited = []
    # dfs는 stack, bfs는 queue개념을 이용한다.
    stack = [root]
    
    while(stack): #스택에 남은것이 없을 때까지 반복
        node = stack.pop() # node : 현재 방문하고 있는 꼭지점
        
        #현재 node가 방문한 적 없다 -> visited에 추가한다.
        #그리고 해당 node의 자식 node들을 stack에 추가한다.
        if(node not in visited):
            visited.append(node)
            stack.extend(graph[node])
    return visited

In [3]:

dfs_iteration(graph,'A')

Out[3]:

['A', 'C', 'H', 'G', 'B', 'E', 'F', 'D']

특히, 재귀(recursive)적으로 구현할 때는
visited.append(node)와 visited = visited + [node]를 상황에 따라 다르게 사용해야 한다.
visited = visited + [node]의 경우, 전자와 후자의 visited가 참조하는 주솟값이 서로 다르기 때문이다.

---

1.방문한 node들을 update하고 싶을 때

• visited.append(node) 를 사용할 것인가?
• visited = visited + [node]를 사용할 것인가?

2. (자기 자신)함수를 호출할 때

• dfs_recursive(graph, node, visited)
• visited = dfs_recursive(graph, node, visited)

어떤 차이가 있을까?
어떤 상황에서 무엇을 사용해야 하는가?

---

재귀(recursive)를 이용해서 DFS 구현하기¶

---

In [4]:

def dfs_recursive(graph, start, visited=[]):
    
    visited.append(start) ## ★★★★★
    
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited) ## ★★★★★
    
    return visited

In [5]:

dfs_recursive(graph, 'A')

Out[5]:

['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H']

In [6]:

# 중간에 print(visited)를 추가
# 함수가 호출될때마다 visited 리스트에 어떤 변화가 있을지 보고 싶다.
def dfs_recursive(graph, start, visited=[]):
    
    visited.append(start)
    print(visited) #추가된 print(visited)
    
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    
    return visited

In [7]:

dfs_recursive(graph,'A')

['A']
['A', 'B']
['A', 'B', 'D']
['A', 'B', 'D', 'E']
['A', 'B', 'D', 'E', 'F']
['A', 'B', 'D', 'E', 'F', 'C']
['A', 'B', 'D', 'E', 'F', 'C', 'G']
['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H']

Out[7]:

['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H']

In [8]:

# 마지막의 return vistied를 제거하면?
def dfs_recursive(graph, start, visited=[]):
    
    visited.append(start)
    print(visited)
    
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    # return 제거

In [9]:

dfs_recursive(graph,'A')

['A']
['A', 'B']
['A', 'B', 'D']
['A', 'B', 'D', 'E']
['A', 'B', 'D', 'E', 'F']
['A', 'B', 'D', 'E', 'F', 'C']
['A', 'B', 'D', 'E', 'F', 'C', 'G']
['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H']

재귀함수이면서 리스트의 변화된 값을 보고 싶으면,
return이 없더라도 문제가 되진 않겠다.

---

In [10]:

def dfs_recursive(graph, start, visited=[]):
    
    visited = visited + [start] ## visited.append(start)대신 visited = visited + [start]를 대입
    
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    
    return visited

In [11]:

# 왜 이런 결과값이 나오는지 궁금하다면, 함수가 호출될때마다 visited에 어떤 변화가 있는지 한번 보도록 하자.
dfs_recursive(graph, 'A')

Out[11]:

['A']

In [12]:

def dfs_recursive(graph, start, visited=[]):
    
    visited = visited + [start] ## visited.append(start)대신 visited = visited + [start]를 대입
    print(visited) # print(visited) 추가
    
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    
    return visited

In [13]:

dfs_recursive(graph, 'A')

['A']
['A', 'B']
['A', 'B', 'D']
['A', 'B', 'E']
['A', 'B', 'E', 'F']
['A', 'C']
['A', 'C', 'G']
['A', 'C', 'H']

Out[13]:

['A']

visited = visited + [node]를 하게 되면
두 visited가 서로 다른 리스트를 참조하게 되므로
재귀 함수를 호출하면서 생기는 많은 함수들이
어떤 하나의 리스트에 모든 결과를 반영하는 것이 아니라
각자 독자적인 리스트를 갖게 되므로 저런 결과가 생기는 것.
각자 독자적인 리스트를 주면서, 앞의 visited.append(node)의 효과를 주고 싶다면
한가지만 더 수정해주면 될 것 같다.

for문 안에 (재귀)함수가 호출되는 부분이 있다.
dfs_recursive(graph, node, visited)를
visited = dfs_recursive(graph, node, visited)로 수정해주자.

In [14]:

def dfs_recursive(graph, start, visited=[]):
    
    visited = visited + [start] ## visited.append(start)대신 visited = visited + [start]를 대입
    print(visited) # print(visited) 추가
    
    for node in graph[start]:
        if node not in visited:
            visited = dfs_recursive(graph, node, visited) # 수정된 부분!
            
    return visited

In [15]:

# 각자 독자적인 list를 갖는 건 마찬가지지만, 전에 일어난 일들을 반영하게 해주는 식.
dfs_recursive(graph, 'A')

['A']
['A', 'B']
['A', 'B', 'D']
['A', 'B', 'D', 'E']
['A', 'B', 'D', 'E', 'F']
['A', 'B', 'D', 'E', 'F', 'C']
['A', 'B', 'D', 'E', 'F', 'C', 'G']
['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H']

Out[15]:

['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H']

DFS 경로 탐색은 어떻게 하는가?¶

예를 들어, A부터 H까지 갈 수 있는 가능한 경로를 모두 알아보고 싶다.
방문 순서를 순서대로 기록할 필요가 있다.
(독자적으로 리스트를 할당받아야 할 것 같다.)

---

In [16]:

# 새로운 graph
graph = {'A':['B','C'],
         'B':['A','D','E'],
         'C':['A','F','G'],
         'D':['B'],
         'E':['B','H'],
         'F':['C','H'],
         'G':['C'],
         'H':['E','F']}

In [17]:

paths = []

def dfs_paths(graph, start, end, visited=[]):
    # 그 전에 방문했던 노드들을 기록하고
    # 이번 차례 방문하는 노드를 새로 추가한다.
    visited = visited + [start]
    
    #도착할 경우, paths에 경로를 기록한다.
    if start == end:
        paths.append(visited)
    
    #현재 노드의 자손 노드들 중, 방문하지 않은 노드들에 대해 재귀 호출
    for node in graph[start]:
        if node not in visited:
            dfs_paths(graph, node, end, visited)

In [18]:

dfs_paths(graph,'A','H')

In [19]:

# graph상에서 A->H로 갈 수 있는 경로는 2가지가 있다.
paths

Out[19]:

[['A', 'B', 'E', 'H'], ['A', 'C', 'F', 'H']]