제주코딩베이스캠프 Python 71 : 깊이 우선 탐색

깊이 우선 탐색이란?

• stack을 이용

---

풀이

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

def dfs(graph, start) :
    visited = list()
    stack = list()

    stack.append(start)

    while stack :
        node = stack.pop()

        if node not in visited :
            visited.append(node)
            stack.extend(graph[node])
    return visited
    
print(dfs(graph,'E'))

출력  : ['E', 'A', 'B', 'C', 'D', 'F']

---

과정

def dfs(graph, start) :
    visited = list()
    stack = list()

    stack.append(start)
    count = 0

    while stack :
        node = stack.pop()

        print(f'{count}번째 current : {node}')
        if node not in visited :
            visited.append(node)
            stack.extend(graph[node])
            print(f'{count}번째 visited : {visited}')
            print(f'{count}번째 stack : {stack}')
            print("")
            count+=1
    return visited  

출력

0번째 visited : ['E']
0번째 stack : ['D', 'A']

1번째 current : A
1번째 visited : ['E', 'A']
1번째 stack : ['D', 'E', 'C', 'B']

2번째 current : B
2번째 visited : ['E', 'A', 'B']
2번째 stack : ['D', 'E', 'C', 'A']

3번째 current : A
3번째 current : C
3번째 visited : ['E', 'A', 'B', 'C']
3번째 stack : ['D', 'E', 'A']

4번째 current : A
4번째 current : E
4번째 current : D
4번째 visited : ['E', 'A', 'B', 'C', 'D']
4번째 stack : ['E', 'F']

5번째 current : F
5번째 visited : ['E', 'A', 'B', 'C', 'D', 'F']
5번째 stack : ['E', 'D']

6번째 current : D
6번째 current : E

최종 : ['E', 'A', 'B', 'C', 'D', 'F']