[자료구조] FloodFill 파이썬 (BFS, queue)

BFS

from collections import deque
def solution(n, m, image):
    cnt = 0
    visited = [[False] * m for _ in range(n)] # visited table (col(m) x row(n))
    dir = [[1,0], [0,1], [-1,0], [0,-1]] # 4-direction
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                q = deque() # BFS-queue
                q.append([i,j])
                visited[i][j] = True
                color = image[i][j]
                while q:
                    x, y = q.popleft()
                    for dx, dy in dir:
                        xx, yy = x+dx, y+dy
                        if 0 <= yy < m and 0 <= xx < n:
                            if not visited[xx][yy]:
                                if image[xx][yy] == color:
                                    visited[xx][yy] = True
                                    q.append([xx,yy])
                cnt += 1
    return cnt

출처의 코드는 x,y를 바꿔서 쓰셨는데

 

나는 x,y 순서가 익숙하다.

 

출처: velog.io/@rapsby/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-FloodFill-python

 

유사 문제

BOJ

1012 유기농 배추 link

 

배추 풀이: DFS

 

유의점

global 선언

 

import sys
sys.setrecursionlimit(10000)

T = int(input())

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

def dfs(x, y):
    global B, ck
    if ck[x][y] == 1: # 체크한 방향 기준 4방향을 살펴봄
        return
    ck[x][y] = 1
    for i in range(4):
        xx, yy = x+dx[i], y+dy[i]
        if B[xx][yy] == 0 or ck[xx][yy] == 1: # 체크점 기준에서 다음으로 갈 곳 (4방향)이 0이거나 체크된 곳이라면 탐색 X
            continue
        dfs(xx,yy)


def process():
    global B, ck
    M, N, K = map(int, input().split())
    # index 방법: 가상의 0을 둘러서 채운다
    # 입력을 받을때 +1 해주면 됨
    B = [[0 for i in range(50+2)] for _ in range(50+2)] # 0을 양쪽에
    ck = [[0 for i in range(50+2)] for _ in range(50+2)] # 0을 양쪽에
    for _ in range(K):
        X, Y = map(int, input().split())
        # 1을 채우기
        B[Y+1][X+1] = 1 # 양쪽에 0을 추가했기 때문에 1을 더한 것부터 시작
    ######## INPUT DONE #########

    # Flood Fill 로 전체탐색을 할 수 밖에 없음 
    # 복잡도는 50*50
    # 탐색한 부분은 재탐색 안하는 것이 중요
    ans = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            if B[i][j] == 0 or ck[i][j] == 1: # ck에 값이 있으면 탐색x
                continue
            dfs(i,j) # 순회탐색
            ans += 1 # 탐색이 되었다면 +1
    print(ans)


for _ in range(T):
    process()