BFS 너비 우선탐색 - 파이썬

 

 

프로그래머스 - 타켓 넘버 를 풀다가 이 구조 자체 이해에 어려움을 느껴서 따로 정리한다.

 

 

 

 

BFS (너비 우선 탐색) : 가까운 노드부터 방문하는 것. 

 

친구 관계가 저렇게 얽혀있다고 생각해보고, A 부터 너비 우선 탐색을 해본다면

 

A → B → E → C → D → G → H → F → J → I 이다. 자세히는...

 

 

 

A → B → E  (A와 붙어있는 애들 왼쪽부터 방문)

 

→ C  → D  (A 왼쪽에 붙어있던 B 와 붙어있는 애들 방문) 

 

→ G (A 오른쪽에 붙어있던 E 와 붙어있는 애 방문)

 

→ H (A 한테 붙은 애들 (B, E) 다 했으니까 B 왼쪽에 붙어있던 C 와 붙어있는 애 방문)

 

→ J → F (B 오른쪽에 붙어있던 D와 붙어있는 애들 방문)

 

→ I (D 한테 붙어있는 J와 붙어있는 애 방문)

 

 

이렇게 너비 우선 탐색은 가까이에 있는 (인접한) 노드를 먼저 방문한다. 

이걸 파이썬으로 검사하도록 하려면...

 

0. graph(dic), visit_wait(list), visit_done(list), node  

1. 딕셔너리의 키와 값을 각 노드와 노드와 이웃한 노드로 정의해준다.

2. 탐색을 원하는 노드를 '방문대기'에 삽입.

3. '방문대기'의 0번째 원소를 POP 해서 node 에 저장.

4. 만약 node 가 '방문완료' 에 포함되어 있다면 pass.

5. 포함되어 있지 않다면 '방문완료'에 node 를 삽입. 

   '방문대기'에 node 의 이웃한 원소들 (graph 의 node 를 키로 쓴 값) 삽입. 

6. '방문대기'에 더이상 아무것도 들어오지 않을 때까지 2번으로 돌아감.

7. 모든 방문을 마치면 '방문완료' 를 반환.

 

 

 

코드

graph = dict()
graph['A'] = ['B', 'E']
graph['B'] = ['A', 'C','D']
graph['C'] = ['B','H']
graph['D'] = ['B', 'J', 'F']
graph['E'] = ['A','G']
graph['F'] = ['D']
graph['G'] = ['E']
graph['H'] = ['C','J']
graph['I'] = ['J']
graph['J'] = ['D','H','I']

def bfs (graph, start_node):

    visit_wait = list()         #방문대기 list
    visit_done = list()            #방문완료 list

    visit_wait.append(start_node)   #첫번째 노드 추가

    while visit_wait :        #방문대기에 뭔가 있으면 계속 실행

        node = visit_wait.pop(0)            #맨 앞에 것 pop
        print("노드:",node)

        if node in visit_done :

            print("이미 탐색함.")

        else:

            visit_done.append(node)
            visit_wait.extend(graph[node])

        print("방문대기:",visit_wait)
        print("방문완료:",visit_done)

    return visit_done


bfs(graph, 'A')

 

 

결과

node: A
방문대기: ['B', 'E']
방문완료: ['A']
node: B
방문대기: ['E', 'A', 'C', 'D']
방문완료: ['A', 'B']
node: E
방문대기: ['A', 'C', 'D', 'A', 'G']
방문완료: ['A', 'B', 'E']
node: A
이미 탐색함.
방문대기: ['C', 'D', 'A', 'G']
방문완료: ['A', 'B', 'E']
node: C
방문대기: ['D', 'A', 'G', 'B', 'H']
방문완료: ['A', 'B', 'E', 'C']
node: D
방문대기: ['A', 'G', 'B', 'H', 'B', 'J', 'F']
방문완료: ['A', 'B', 'E', 'C', 'D']
node: A
이미 탐색함.
방문대기: ['G', 'B', 'H', 'B', 'J', 'F']
방문완료: ['A', 'B', 'E', 'C', 'D']
node: G
방문대기: ['B', 'H', 'B', 'J', 'F', 'E']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G']
node: B
이미 탐색함.
방문대기: ['H', 'B', 'J', 'F', 'E']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G']
node: H
방문대기: ['B', 'J', 'F', 'E', 'C', 'J']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H']
node: B
이미 탐색함.
방문대기: ['J', 'F', 'E', 'C', 'J']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H']
node: J
방문대기: ['F', 'E', 'C', 'J', 'D', 'H', 'I']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J']
node: F
방문대기: ['E', 'C', 'J', 'D', 'H', 'I', 'D']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F']
node: E
이미 탐색함.
방문대기: ['C', 'J', 'D', 'H', 'I', 'D']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F']
node: C
이미 탐색함.
방문대기: ['J', 'D', 'H', 'I', 'D']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F']
node: J
이미 탐색함.
방문대기: ['D', 'H', 'I', 'D']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F']
node: D
이미 탐색함.
방문대기: ['H', 'I', 'D']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F']
node: H
이미 탐색함.
방문대기: ['I', 'D']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F']
node: I
방문대기: ['D', 'J']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F', 'I']
node: D
이미 탐색함.
방문대기: ['J']
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F', 'I']
node: J
이미 탐색함.
방문대기: []
방문완료: ['A', 'B', 'E', 'C', 'D', 'G', 'H', 'J', 'F', 'I']

 

이 코드에서 주의해야 할 점은...

노드를 방문한 건지 아닌지를 먼저 확인해야 한다는 것이다.

 

예를 들면 node 가 E 이면, 

E와 붙어있는 A 와 G 가 visit_wait 리스트에 들어간다.

하지만 A는 가장 처음 방문해 visit_done 리스트에 포함되어 있으니까

A의 차례가 오더라도 이미 탐색한 것이라고 알고 탐색하지 않는다.

 

 

이 너비 우선 탐색이 직관적이지 않아서 

전체 탐색 과정을 print 로 봐서야 이해가 되었다.