[프로그래머스 - BFS] FloodFill

초기 변수 설정 

1.  check[][] : n*m 사이즈의 boolean 타입 2D Array
   • BFS과정에서 grouping 완료된 좌표 => True
2.  queue : 현재 바라볼 좌표(x,y)를 pop, 바라보는 좌표의 이웃들 (x-1, y) (x+1, y) (x, y-1) (x, y+1)을 append

로직

1. 이중 for 문으로 n*m 사이즈의 좌표를 차례로 탐색
2. if check하지 않은 좌표
   • 해당 좌표를 bfs 탐색하며 grouping 한 후 count +=1 해준다.
   • (BFS 탐색 한 번 == grouping 한 번)
3. return count

BFS 탐색

1. queue.append(탐색 시작 좌표)
2. while queue is not empty:
   1. queue.popleft() # 현재 바라봐야할 좌표 pop
   2. if 해당 좌표가 시작 좌표의 컬러와 같고 아직 check되지 않은 좌표라면
      • check as True
      • 해당 좌표의 이웃들 (x-1, y) (x+1, y) (x, y-1) (x, y+1) append
   3. return 1 # grouping 한 번 완료

 

코드

from collections import deque

def solution(n, m, image):
    check = [[False] * m for i in range(n)]
    answer = 0
    for x in range(n):
        for y in range(m):
            if not check[x][y]:
                answer += bfs(image, check, (x, y), n, m)
                # check[x][y] = True

    return answer


def bfs(image, check, point, n, m):
    queue = deque([point])
    start_x, start_y = point
    start_color = image[start_x][start_y]

    while queue:
        x, y = queue.popleft()

        if start_color == image[x][y] and not check[x][y]:
            check[x][y] = True

            if 0 < x:
                queue.append((x - 1, y))
            if x < n-1:
                queue.append((x + 1, y))
            if 0 < y:
                queue.append((x, y - 1))
            if y < m-1:
                queue.append((x, y + 1))

    return 1

 

 

TIP

collections.deque

from collections import deque

# 선언
queue = deque([])

# pop
queue.popleft()

# push
queue.append()

list 보다 deque 원소의 pop, push가 빠르다

(list는 내부적으로 pop, push할 때 나머지 원소들을 한 칸씩 이동시켜야 하기 때문이다 : O(n))

 

 

2D Array in Python

 array_2d = [[False]*(n) for i in range(m)]

N * M 사이즈의 2D Array를 만들기 위해서는 위와 같은 방식을 사용해야한다

 

array_2d = [[False] *m]*n

두 번째 방식은 동일한 객체를 n번 반복하여 만드는 것이기 때문에

하나의 요소를 수정하게 되면 모든 행에도 변경사항이 적용된다.

 

 

 

아래의 사이트에서 flood fill을 잘 설명해주어 도움이 많이 되었다.

blog.encrypted.gg/729

[실전 알고리즘] 0x05강 - BFS, DFS_구버전