LeetCord - 733. Flood Fill

이미지는 m x n 크기의 정수 그리드인 image로 표현됩니다.

image[i][j]는 이미지의 픽셀 값입니다.

또한 세 개의 정수 sr, sc, color가 제공됩니다. 이미지[sr][sc]에서 시작하여 이미지에 대해 flood fill 작업을 수행해야 합니다.

flood fill을 수행하기 위해서는 시작 픽셀과 동일한 색상을 가진 시작 픽셀과 4방향으로 연결된 모든 픽셀, 그리고 그 픽셀들과 4방향으로 연결된 모든 픽셀들(또한 같은 색상)을 고려합니다. 이들 모든 픽셀의 색상을 color로 바꿉니다.

flood fill을 수행한 후 수정된 이미지를 반환합니다.

 

1. BFS 탐색 준비하기

• 상하좌우 이동방향이 들어있는 배열을 만듭니다.
• 방문처리할 image의 크기만큼 bool 배열을 만듭니다.
• 시작지점을 미리 방문 처리하고 시작위치의 색을 바꿔줍니다.
• 다음 이동위치를 저장할 큐를 만듭니다.
• 시작위치를 큐에 넣습니다.

2. 탐색 시작

• 탐색 종료 조건은 더이상 이동할 위치가 없는 경우 입니다.
• 큐에 넣어놓은 위치를 가져와 이동할 위치값을 구하고 image 배열 안에 있으면서 방문하지 않았고 본래 색과 똑같다면 다음 방문위치의 색을 바꿔준뒤 방문처릴해주고 큐에 넣어줍니다.

 

public class Solution
{
    public int[][] FloodFill(int[][] image, int sr, int sc, int color)
    {

        int originColor = image[sr][sc];
        int imageRow = image.Length;
        int imageCol = image[0].Length;

        int[,] move = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        bool[,] visited = new bool[imageRow, imageCol];
        visited[sr, sc] = true;
        image[sr][sc] = color;
        
        Queue<Coord> coords = new Queue<Coord>();
        coords.Enqueue(new Coord(sr, sc));

        while (coords.Count > 0)
        {
            Coord coord = coords.Dequeue();

            for (int i = 0; i < 4; i++)
            {
                int nx = coord.X + move[i, 0];
                int ny = coord.Y + move[i, 1];

                if (nx >= 0 && ny >= 0 && nx < imageRow && ny < imageCol && image[nx][ny] == originColor && !visited[nx, ny])
                {
                    image[nx][ny] = color;
                    visited[nx, ny] = true;
                    coords.Enqueue(new Coord(nx, ny));
                }
            }
        }
        return image;
    }

    struct Coord
    {
        public int X;
        public int Y;

        public Coord(int _x, int _y)
        {
            X = _x;
            Y = _y;
        }
    }
}