제주코딩베이스캠프 Python 72 : 너비 우선 탐색

이하연·2020년 8월 15일
0

너비 우선 탐색이란?

  • queue을 이용


풀이

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

def bfs(graph,start) :
    visited = list()
    queue = list()

    queue.append(start)

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited
    
print(bfs(graph,'E'))
출력  : ['E', 'D', 'A', 'F', 'C', 'B']

과정

def bfs(graph,start) :
    visited = list()
    queue = list()

    queue.append(start)
    count = 0

    while queue:
        node = queue.pop(0)
        print(f'{count}번째 current : {node}')

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

    return visited
출력

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

1번째 current : D
1번째 visited : ['E', 'D']
1번째 queue : ['A', 'E', 'F']

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

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

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

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

6번째 current : D
6번째 current : A
6번째 current : A

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

0개의 댓글