[알고리즘] 너비 우선 탐색 (+LeetCode 733)

BFS (breadth first search, 너비 우선 탐색)는 tree 혹은 graph 형태의 data structure에서 일종의 조건을 만족하는 node를 찾는 알고리즘. 

Tree:

• Tree는 node(동그라미)와  edge(선)로 이뤄져 있다. 
• Root node (1번 동그라미)에서부터 edge들로 가지를 쳐가는 형태로 데이터가 정렬되어 있다.
• 각 node는 여러 개의 child node (그림에서 더 밑쪽에 있는 node)와 연결될 수 있지만 단 한 개의 parent node와 연결될 수 있다.

Graph:

• 비슷하게 node, edge로 이뤄져 있다
• 두node간 edge로 연결되어 있을 수 있다. Parent, child node 개념이 없다.

BFS는 말 그대로 너비 우선 탐색하는 방식인데, tree에 대해서 이해하는 작동 원리를 보면 이해하기 쉽다: 첫 번째 layer에서 출발해서 각 layer들을 왼쪽 node부터 탐색한다.
위 그림에서는 [1] -> [2 -> 3 -> 4] -> [5 -> 6 -> 7]번 순서대로 탐색한다.

구현할 때는 first in first out queue 를 사용한다 (가장 먼저 들어간 node가 가장 먼저 나오는 구조).

 

Pseudo code를 살펴보자. G는 graph/tree, root = root node, v = node

 1  procedure BFS(G, root) is
 2      let Q be a queue # 방문해야 하는 node 저장 용도
 3      label root as explored # 탐색한 node 저장 용도
 4      Q.enqueue(root) # root node부터 탐색
 5      while Q is not empty do # 탐색할 node가 없을 때 까지
 6          v := Q.dequeue()
 7          if v is the goal then 
 8              return v # 조건 만족하면 탈출
 9          for all edges from v to w in G.adjacentEdges(v) do 
10              if w is not labeled as explored then # 탐색 안한 경우
11                  label w as explored # 탐색했다고 라벨
12                  w.parent := v # parent node의 정보 저장
13                  Q.enqueue(w) # queue 저장

간단한 문제를 하나 풀어보는 것이 이해에 도움이 된다.

https://leetcode.com/problems/flood-fill/

 

간단 설명: 이미지가 있고 (list) 시작점과 새로 색칠할 색이 주어진다. 이 시작점의 왼쪽/오른쪽/위/아래의 점이 시작점과 같은 색이면 연결된 점이라고 하자. 이렇게 연결된 모든 점들을 주어진 색으로 색칠한다. 

BFS로 풀어보자 (효율적인 풀이는 아님):

from queue import Queue
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        h, w = len(image),len(image[0]) # 높이, 너비
        visited = set() # 탐색했는지 확인할 때 사용
        directions = [(1,0), (0,1), (-1,0), (0,-1)] # 탐색 가능한 방향
        add_direction = lambda pos,direction: (pos[0]+direction[0],pos[1]+direction[1]) # 위치에 방향 더해주는 함수
        q = Queue()
        cur_pos = (sr,sc) # 현제 위치
        visited.add(cur_pos)  # 시작점은 탐색했다고 마킹
        start_color = image[sr][sc] # 시작점 색
        q.put(cur_pos) # 시작점부터 탐색
        while not q.empty():
            cur_pos = q.get() # 현제 위치
            image[cur_pos[0]][cur_pos[1]] = color # 현제 위치 색칠
            for direction in directions:
                next_pos = add_direction(cur_pos,direction) # 다음 위치
                if ((0 <= next_pos[0] < h) and (0 <= next_pos[1] < w)) \ # 이미지 내부에 있고
                    and (not next_pos in visited) \ # 방문 안했으며
                    and (image[next_pos[0]][next_pos[1]] == start_color): # 같은 색일 때만 다음 위치 탐색
                    q.put(next_pos) # 다음 위치를 queue에 추가
                    visited.add(next_pos) # 다음 위치를 방문했다고 마킹
        return image

 

Ref. 

https://en.wikipedia.org/wiki/Breadth-first_search