Flood Fill

문제

2차원 정수 배열 image와 시작 좌표 sr, sc, 그리고 새로운 색상 color가 주어집니다. image는 화면의 픽셀을 나타내며 각 값은 픽셀의 색상입니다. 시작 픽셀 (sr, sc)에서 출발하여 상하좌우 4방향으로 연결되어 있으면서 시작 픽셀과 같은 색상을 가진 모든 픽셀의 색상을 새로운 색상(color)으로 변경하는 '플러드 필(Flood Fill)' 작업을 수행하는 문제입니다. 그림판의 '색 채우기' 기능과 동일하게 동작합니다.

• 입력: 2차원 배열 image (크기 1 이상 50 이하), 시작 좌표 sr, sc, 새로운 색상 color
• 출력: 플러드 필 작업이 완료된 2차원 배열 image

링크: https://leetcode.com/problems/flood-fill

풀이 1: Queue와 방문 배열을 활용한 BFS 탐색

너비 우선 탐색(BFS)을 사용하여 시작점으로부터 인접한 픽셀들을 큐에 넣어가며 탐색하는 방식입니다.

• 방문 배열 활용: 무한 루프를 방지하기 위해 image와 동일한 크기의 boolean[][] visited 배열을 선언하여 방문한 좌표를 기록합니다.
• 너비 우선 탐색 (BFS): 
  • 큐에서 현재 좌표를 꺼낸 뒤 상하좌우 4방향을 탐색합니다.
  • 배열의 범위를 벗어나지 않고, 아직 방문하지 않았으며, 원본 색상(image[y][x])과 동일한 색상을 가진 인접 픽셀만 큐에 넣고 방문 처리합니다.
• 색상 변경: 탐색이 모두 끝난 후, visited 배열을 순회하며 true로 표시된 픽셀들만 한꺼번에 새로운 color로 변경해 줍니다.

코드 1

import java.util.*;

class Solution {
    int[] dy = {-1, 0, 1, 0};
    int[] dx = {0, 1, 0, -1};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int n = image.length;
        int m = image[0].length;
        
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sr, sc});
        visited[sr][sc] = true;

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int y = cur[0];
            int x = cur[1];
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                if (visited[ny][nx] || image[ny][nx] != image[y][x]) continue;
                q.add(new int[]{ny, nx});
                visited[ny][nx] = true;
            }
        }

        // 방문한 모든 지점의 색상을 한 번에 변경
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(visited[i][j]) image[i][j] = color;
            }
        }

        return image;
    }
}

풀이 2: 재귀(Recursion)를 활용한 DFS 탐색

깊이 우선 탐색(DFS)을 사용하여 추가적인 큐나 방문 배열 없이 원본 배열을 직접 수정(In-place)하며 탐색하는 최적화된 방식입니다.

• 무한 루프 방지 (예외 처리): 변경하려는 새로운 색상(color)이 이미 시작 픽셀의 색상과 동일하다면, 칠할 필요가 없을 뿐만 아니라 무한 재귀에 빠질 수 있습니다. 따라서 if (image[sr][sc] == color) return image; 로직을 통해 조기 종료합니다.
• 깊이 우선 탐색 (DFS): * 재귀 함수 내부에서 현재 좌표가 배열 범위를 벗어났거나, 칠해야 할 기존 색상(color)이 아니라면 즉시 반환(return)합니다.
  • 조건을 통과했다면 현재 픽셀을 새로운 색상(newColor)으로 즉시 덮어씁니다. 이 작업이 방문 배열(visited)의 역할을 대신하므로 중복 방문을 막을 수 있습니다.
  • 이후 상하좌우 4방향에 대해 재귀 호출을 수행합니다.

코드 2

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // 이미 칠하려는 색상과 동일하다면 무한루프 방지를 위해 즉시 반환
        if (image[sr][sc] == color) return image;
        
        dfs(image, sr, sc, image[sr][sc], color);
        return image;
    }

    void dfs(int[][] image, int sr, int sc, int color, int newColor) {
        // 배열 범위를 벗어나거나 기존 색상과 다르면 종료 (기저 조건)
        if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length || image[sr][sc] != color) return;
        
        // 새로운 색상으로 덮어씌움 (방문 처리 역할 동시 수행)
        image[sr][sc] = newColor;
        
        // 4방향 재귀 탐색
        dfs(image, sr - 1, sc, color, newColor);
        dfs(image, sr + 1, sc, color, newColor);
        dfs(image, sr, sc - 1, color, newColor);
        dfs(image, sr, sc + 1, color, newColor);
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)