[알고리즘] Flood Fill(Seed Fill)-BFS

플러드 필(Flood Fill)이란?

다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 해당 알고리즘은 그림판의 채우기 기능과 지뢰 찾기 프로그램에 이용된다. 주변에 같은 성질을 가지는 셀을 모두 찾아준다는 공통점이 있다.

플러드 필은 보통 DFS(재귀)와 BFS(Queue)를 이용하여 구현한다. 이 포스팅에서는 BFS를 이용한 구현을 알아볼 것이다.

💡예시 코드

# 섬의 개수, 최대 섬의 크기, 최소 섬의 크기 구하기
from collections import deque

N = int(input())
arr = [list(input()) for _ in range(N)]
cnt = 0
Max, Min = -21e8, 21e8

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def bfs(y, x):
    global Max, Min
    q = deque()
    q.append([y, x])
    arr[y][x] = '0'
    size = 1
    while q:
        node = q.popleft()
        a, b = node[0], node[1]
        for i in range(4):
            ny = dy[i] + a
            nx = dx[i] + b
            if not (0<=ny<N and 0 <=nx<N): continue
            if arr[ny][nx] == '0': continue
            arr[ny][nx] = '0'
            q.append([ny,nx])
            size += 1
    return size

for i in range(N):
    for j in range(N):
        if arr[i][j] == '1':
            cnt += 1
            result = bfs(i,j)
            Min = min(Min, result)
            Max = max(Max, result)

print(Min, Max) # 가장 작은 섬, 가장 큰 섬의 크기       
print(cnt) # 섬의 개수

'''
입력
5
01100
00010
11011
01010
10000

출력
1 4 # 최소, 최대 사이즈
4   # 섬의 개수
'''

# 최대 섬에서 최소 섬의 최단 거리 구하기 (위 문제 응용)
from collections import deque

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

cnt = 1 # 이 값으로 섬의 영역을 치환, 값이 1과 겹치지 않게 1로 시작 
Max, Min = -21e8, 21e8

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def bfs(y, x, cnt): # 섬의 영역을 다른 숫자로 바꾸고, size 출력
    global arr
    q = deque()
    q.append([y, x])
    arr[y][x] = cnt
    size = 1
    while q:
        node = q.popleft()
        a, b = node[0], node[1]
        for i in range(4):
            ny = dy[i] + a
            nx = dx[i] + b
            if not (0<=ny<N and 0 <=nx<N): continue
            if arr[ny][nx] != 1: continue ## 중요
            arr[ny][nx] = cnt
            q.append([ny,nx])
            size += 1
    return size

def find_path(y, x): # Max_num이 있는 좌표까지의 최단 거리 리턴
    used = [[False]*N for _ in range(N)]
    que = deque()
    que.append([y, x, 0]) # 0은 level
    used[y][x] = True
    while que:
        a, b, level = que.popleft()
        if arr[a][b] == Max_num:
            return level
        for i in range(4):
            ny = dy[i] + a
            nx = dx[i] + b
            if not (0<=ny<N and 0 <=nx<N): continue
            if arr[ny][nx] == Min_num: continue ## 중요
            que.append([ny,nx,level+1])

for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            cnt += 1 
            result = bfs(i,j,cnt) # 섬의 영역을 다른 숫자로 바꾸고, size 출력
            if Min > result: 
                Min = result
                Min_num = cnt # 최소 섬에 넣어준 값을 표시
            if Max < result:
                Max = result
                Max_num = cnt # 최대 섬에 넣어준 값을 표시

answer = 21e8
for i in range(N):
    for j in range(N):
        if arr[i][j] == Min_num:
            tmp = find_path(i,j)
            answer = min(answer, tmp)

print(answer)

'''
입력
5
0 1 1 0 0
0 0 0 1 0
1 1 0 1 1
0 1 0 1 0
1 0 0 0 0

출력
4
'''

💡응용 문제

# 벽(1)은 최대 두 번 부술 수 있으며 tank -> prince로 가는 최소 이동 횟수 구하기
from collections import deque

map = [
    [0,0,1,1,1,1],
    [0,0,1,0,0,1],
    [0,0,1,0,1,1],
    [0,0,1,0,1,0]
]

tank = [0,0]
prince = [3,5]

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def bfs():
    q = deque()
    q.append([tank[0],tank[1],0,0]) # 마지막 두 개 level, crack
    # used = [[False]*6 for _ in range(4)]
    # used[tank[0]][tank[1]] = True

    while q:
        y, x, level, crack = q.popleft()
        if y == prince[0] and x == prince[1]: 
            break
        for i in range(4):
            ny = dy[i] + y
            nx = dx[i] + x
            if not (0<=ny<4 and 0<=nx<6): continue
            # if used[ny][nx] == True: continue

            if map[ny][nx] == 1: 
                crack += 1
                if crack <= 2:
                    # used[ny][nx] = True
                    q.append([ny,nx,level+1,crack])
            else:
                # used[ny][nx] = True
                q.append([ny,nx,level+1,crack])

    return level

print(bfs()) # 8

'''
주의 사항
used 배열을 쓰면 안되는 이유: 
경로가 여러가지 존재하는데 단순히 used 배열을 하나만 쓰면 그 경로마다 used 상태가 다른 것이 반영이 안된다. 
그래서 단순 최단 거리만 구하는 것이니까 used를 쓰지 않거나, used 배열을 queue에 append하여 상태를 존재하는 경로 별로 관리해야 한다.
'''

💡Flood Fill 활용 문제

• 백준
  • 줄 세우기
  • 작업
  • 유기농 배추
• 프로그래머스
  • FloodFill