Flood Fill (C#)

이중 배열, 시작 위치, 변경한 색상 값을 입력받습니다.

시작 필셀부터 시작해서 인접해 있는 픽셀의 색상값을 변경할 때, 최종적인 이미지의 모습을 반환해주세요

(시작 위치의 색상과 같은 색상만 변경할 수있습니다.)

 

풀이 방법

BFS(넓이 우선 탐색)을 이용하여 풀이합니다. 

Queue<(int, int)> q = new Queue<(int, int)>();
q.Enqueue((sr, sc));

Queue에 위치 값을 넣고 인접한 픽셀의 위치값으로 이동하는 방식으로 진행합니다

(int, int)는 Tuple입니다.

 

int myColor = image[sr][sc];
image[sr][sc] = color;

색상을 채울 기존의 컬러를 저장하고, 다음 컬러를 시작 위치에 넣습니다.

 

int[] dy = new int[4]{1, -1, 0, 0};
int[] dx = new int[4]{0, 0, 1, -1};
    
while(q.Count() > 0)
{
    var cur = q.Dequeue();
    int cy = cur.Item1;
    int cx = cur.Item2;

    for (int i = 0; i < 4; i++)
    {
        int ny = cy + dy[i];
        int nx = cx + dx[i];

        if (0 > ny || ny >= image.Length || 0 > nx || nx >= image[0].Length)
            continue;

        int nxtColor = image[ny][nx];
        if (nxtColor != myColor || nxtColor == color)
            continue;

        q.Enqueue((ny, nx));
        image[ny][nx] = color;
    }
}

Queue가 비어있게 될 때 까지 반복하여 수행합니다. dy배열과 dx배열을 이용하여 다음 위치 값을 찾고 

해당 위치값이 배열을 벗어나지 않았으며, 변경시킬 컬러값이라고 한다면,

Queue에 다음 위치값을 집어넣고 image의 컬러값을 바꿔줍니다.

 

반복문이 종료되면 인접한 위치의 컬러값이 모두 바뀌게 됩니다.

 

정답 코드

public class Solution 
{
    int[] dy = new int[4]{1, -1, 0, 0};
    int[] dx = new int[4]{0, 0, 1, -1};
    
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) 
    {
        Queue<(int, int)> q = new Queue<(int, int)>();
        q.Enqueue((sr, sc));

        int myColor = image[sr][sc];
        image[sr][sc] = color;
        
        while(q.Count() > 0)
        {
            var cur = q.Dequeue();
            int cy = cur.Item1;
            int cx = cur.Item2;

            for (int i = 0; i < 4; i++)
            {
                int ny = cy + dy[i];
                int nx = cx + dx[i];

                if (0 > ny || ny >= image.Length || 0 > nx || nx >= image[0].Length)
                    continue;

                int nxtColor = image[ny][nx];
                if (nxtColor != myColor || nxtColor == color)
                    continue;
                
                q.Enqueue((ny, nx));
                image[ny][nx] = color;
            }
        }

        return image;
    }
}