[Python] 프로그래머스 Lv 3 - FloodFill

그놈의 BFS ! DFS ! 제발 좀 익숙해지고 싶다.(1)

프로그래머스 Lv 3 - FloodFill 문제풀이

 

알고리즘

한 점에서 시작해서 Image의 값이 같은 것을 모두 탐사하고 갈 수 있는 칸이 없으면 들어간 칸을 내역을 모두 돌려주고 return 하고 안 간 칸을 찾아야 한다.

BFS를 시전하면 된다.

단계별로 정리하면 다음과 같다.

(1) Image 크기 만큼 방문 내역을 만든다.
(2) 첫 칸부터 bfs로 탐사를 보낸다.
(3) 갈 수 있는 칸들은 모두 queue에 넣는다.
 이 때, 이동 가능 검사를 해줘야 한다. 상하, 좌우로 인덱스를 넘어가지 않는지, 방문 한적이 있는데 또가는건 아닌지, 이미지 색이 같은지 4가지를 모두 검사해야 한다.
(4) 이미지가 같다면, 더 갈 수 있으므로 queue에 또 넣는다.
(5) queue가 비면 갈 수 있는 칸은 다 갔다. 즉 1개의 영역을 찾았으므로 1을 리턴하고, 갱신된 방문내역으로 새로 bfs를 한다.

갱신된 방문 내역이 유지되는 이유는 리스트는 mutable하다. 잊지말자!

코드

from collections import deque
def bfs(start, image, visited):
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    move = deque()
    move.append(start)
    
    color = image[start[0]][start[1]]
    while move:
        y, x = move.popleft()
        visited[y][x] = 1
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny < len(image) and 0 <= nx < len(image[0]) and not visited[ny][nx] and image[ny][nx] == color:
                visited[ny][nx] = 1
                move.append([ny, nx])
    return 1

def solution(n, m, image):
    visited = [[0 for _ in range(m)] for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                answer += bfs([i, j], image, visited)
    return answer