플러드 필(flood fill)

플러드 필 알고리즘은 다차원 배열의 어떤 연결된 영역을 찾는 알고리즘이다.

 

시간복잡도: 0(N)

 

BFS나 DFS 둘 다 그래프 자료구조에서 모든 노드를 방문하기 때문에 둘다 플러드필을 구현 가능하다.

 

둘중 하나인 BFS만으로 flood fill을 구현 해보기 위해 예제를 만들어 진행을 해 보겠다.

---

ex) 0으로만 이루어진 2차원배열에 어느 한 점이 1이다

[[0,0,0,0],
 [0,0,0,0],
 [0,1,0,0],
 [0,0,0,0]]

이를 상하좌우로 한칸씩 움직이며 0인 구역을 기준배열에 +1 을 진행을 시켜본다.

[[4,3,4,5],
 [3,2,3,4],
 [2,1,2,3],
 [3,2,3,4]]

이를 만들기 위한 flood fill 예제코드는

arr=[[0,0,0,0],
    [0,0,0,0],
    [0,1,0,0],
    [0,0,0,0]]

def bfs(start):
    q = []
    q.append(start)
    # 상하좌우 움직임을 나타내주는 direct배열
    directy = [-1,1,0,0]
    directx = [0,0,-1,1]
    while q:
        nowy,nowx,nowlevel  =q.pop(0)

        for i in range(4):
            dy = directy[i] + nowy
            dx = directx[i] + nowx
            
            if 0<=dy<4 and 0<=dx<4:
                # arr[dy][dx]자리에 숫자가 없는 경우 숫자를 넣어줌
                if arr[dy][dx] ==0:
                    arr[dy][dx] = nowlevel+1
                    q.append((dy,dx,nowlevel+1))

bfs((2,1,1)) # (y좌표, x좌표, arr[y][x]의값)
# 출력
for y in range(4):
    for x in range(4):
        print(arr[y][x],end=' ')
    print()

출력은 이렇게 된다.

4 3 4 5 
3 2 3 4 
2 1 2 3 
3 2 3 4