C# - Flood Fill

🖌️ 문제 733. Flood Fill

🔸 문제 설명

2차원 배열 image가 주어지고,

어떤 **시작 좌표 (sr, sc)**와 새로운 색상 newColor가 주어졌을 때,

시작 좌표에서 연결된 같은 색상의 픽셀들을 모두 찾아서,

해당 픽셀들을 newColor로 바꾸는 Flood Fill 알고리즘을 구현하라는 문제야.

---

🔹 입력

• image: 2차원 배열 (각 원소는 색상을 의미하는 정수)
• sr, sc: 시작 픽셀의 행(row), 열(column)
• newColor: 바꿀 색상 (정수)

---

🔹 조건

• 연결된 픽셀은 상하좌우로 인접하면서 같은 색을 가진 픽셀만 포함됨
• 대각선은 포함되지 않음 ❌

---

🧪 예시

Input:
image = [[1,1,1],
         [1,1,0],
         [1,0,1]],
sr = 1, sc = 1, newColor = 2

Output:
[[2,2,2],
 [2,2,0],
 [2,0,1]]

설명:

• 시작점 (1,1)의 색은 1
• 이 색과 연결된 상하좌우 방향의 픽셀을 찾아서 2로 바꿈
• image[2][2]은 색이 1이지만 연결되지 않았기 때문에 제외

---

🎯 목표

시작점과 연결된 모든 같은 색의 픽셀을 찾아서, 모두 newColor로 바꾼 2차원 배열을 리턴하는 함수 구현하기!

---

💡 핵심 개념

• Flood Fill은 대표적인 그래프 탐색 문제야.
• 방식은 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색) 중 하나를 사용해 구현할 수 있어.
• DFS가 간단하고 구현도 쉬워서 자주 사용돼.

public class Program
{
    public static void Main(string[] args)
    {
        // 이미지 배열 예시 선언 (2차원 배열)
        int[][] image = new int[][]
        {
            new int[] {1, 1, 1},
            new int[] {1, 1, 0},
            new int[] {1, 0, 1}
        };

        // 시작 위치와 새 색상 정의
        int sr = 1;
        int sc = 1;
        int newColor = 2;

        Console.WriteLine("Before Flood Fill:");
        PrintImage(image);

        FloodFill(image, sr, sc, newColor);

        Console.WriteLine("\\nAfter Flood Fill:");
        PrintImage(image);
    }

    public static void FloodFill(int[][] image, int sr, int sc, int newColor)
    {
        int originalColor = image[sr][sc];

        if (originalColor == newColor)
        {
            return;
        }

        void Fill(int row, int col)
        {
            if (row < 0 || row >= image.Length || col < 0 || col >= image[0].Length)
                return;

            if (image[row][col] != originalColor)
                return;

            image[row][col] = newColor;

            Fill(row - 1, col); // 위
            Fill(row + 1, col); // 아래
            Fill(row, col - 1); // 왼쪽
            Fill(row, col + 1); // 오른쪽
        }

        Fill(sr, sc);
    }

    public static void PrintImage(int[][] image)
    {
        for (int i = 0; i < image.Length; i++)
        {
            for (int j = 0; j < image[i].Length; j++)
            {
                Console.Write(image[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}