Flood Fill : 문제 번호 733 (C#)

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

 

"Flood Fill" 문제는 주어진 2D 이미지에서 특정 위치 (sr, sc)를 시작으로 상, 하, 좌, 우로 연결된 같은 색상의 픽셀을 새로운 색상으로 바꾸는 문제입니다. 여기서 중요한 점은 변경하려는 픽셀이 원래 색상과 같아야 한다는 것입니다.

 

 

가운데 1과 수평, 수직으로 인접한 4개 중에 시작색상이 같은 것들은 가운데 숫자를 바꾼 뒤에도 색상이(숫자가) 같아야 하며, 더이상 변화가 없을때까지 반복실행한다

 

위의 예시로 보면, 가운데 1이니까 왼쪽 

아마 2차원 배열 또는 1차원 배열로 생각해야 할 것 같은데

arr[0][0] 부터 arr[2][2] 까지 있다고 하면

 

arr[1][1]을 최상위 부모로 한다

arr[1][0]과 arr[0][1]을 자식으로 한다

arr[1][0]은 arr[0][0], arr[2][0]을 자식으로 한다

 

행이 같은 것을 찾아서 자식으로 연결하고, 열이 같은거를 찾아서 자식으로 연결하는 과정이 필요하다

재귀호출을 해야 할 것이다

 

        static public int[][] FloodFill(int[][] image, int sr, int sc, int color)
        {
            int temp = image[sr][sc];   /// 기존의 값 저장
            image[sr][sc] = color;      // 새로운 값 갱신
...

sr은 x좌표, sc는 y좌표의 개념이다

 

먼저 시작점의 색상값을 temp에 저장한다

그리고 시작점의 색을 변경

 

이제 그 점의 상하좌우의 색을 temp(기존의 색)과 비교하여 같았던 경우에 한해 색을 바꾼다

            if (sr - 1 >= 0 && (image[sr - 1][sc] == temp)) // 왼쪽 
            {
                //image[sr - 1][sc] = color;
                FloodFill(image, sr - 1, sc, color); /// 왼
            }

가운데 주석친 부분은 최초 1회 호출시 색이 변하는 것을 확인하기 위한 디버그 코드로 제출할때는 제외했다

먼저 왼쪽의 점을 비교하여 색상이 같으면 바꾼다

이를 그 지점에서도 계속 해야하므로 재귀호출

 

            if (sr + 1 < image.Length && (image[sr + 1][sc] == temp))
            {
                //image[sr + 1][sc] = color;
                FloodFill(image, sr + 1, sc, color); /// 오른
            }
            // 
            if (sc - 1 >= 0 && (image[sr][sc - 1] == temp))
            {
                //image[sr][sc - 1] = color;
                FloodFill(image, sr, sc - 1, color); /// 위
            }
            if (sc + 1 < image[sc].Length && (image[sr][sc + 1] == temp))
            {
                //image[sr][sc + 1] = color;
                FloodFill(image, sr, sc + 1, color); /// 아래
            }

같은 방법으로 나머지 방향에서도 진행한다

 

 

1트

        static public int[][] FloodFill(int[][] image, int sr, int sc, int color)
        {
            int temp = image[sr][sc];   /// 기존의 값 저장
            image[sr][sc] = color;      // 새로운 값 갱신

            // 가로, 세로 경계를 넘을 수 없다
            // 기존의 값과 비교해서 같았던 경우에만 새로운 값으로 갱신
            // 확인해야할 것은 4방향
            if (sr - 1 >= 0 && (image[sr - 1][sc] == temp)) // 왼쪽 
            {
                //image[sr - 1][sc] = color;
                FloodFill(image, sr - 1, sc, color); /// 왼
            }
            if (sr + 1 < image.Length && (image[sr + 1][sc] == temp))
            {
                //image[sr + 1][sc] = color;
                FloodFill(image, sr + 1, sc, color); /// 오른
            }
            // 
            if (sc - 1 >= 0 && (image[sr][sc - 1] == temp))
            {
                //image[sr][sc - 1] = color;
                FloodFill(image, sr, sc - 1, color); /// 위
            }
            if (sc + 1 < image[sc].Length && (image[sr][sc + 1] == temp))
            {
                //image[sr][sc + 1] = color;
                FloodFill(image, sr, sc + 1, color); /// 아래
            }
            return image;
        }

 

정상출력되었다

 

visual studio에서는 괜찮은데 제출하는 곳에서는 stack overflow라고한다

왜 그런지는 모르겠지만...

재귀호출로 하니까 실행 횟수가 너무 많았던것같다

그것 때문에 시간초과로 정답이 아닌 듯

 

 

깊이우선탐색(DFS) 방법을 써서 호출 횟수를 줄여야겠다

 

바로 전 84번 문제를 풀때 배열의 인덱스를 스택에 저장했다

여기서도 2차원 배열의 인덱스를 스택에 저장하면 좋겠다

Stack<(int, int)> stack = new Stack<(int, int)>();

이런 것이 가능하더라

 

그러면, 인덱스를 비교해서 색깔이 바뀌는 것들만 스택에 추가하면 되는데

 

저번에는 스택에 넣는 조건과 스택에서 뺴는 조건이 있어서

스택 안에 더이상 없을 때까지 while 문에서 반복했다(pop을 먼저 하고 push)

84번의 조건을 다시 생각해보자

스택에서 pop조건: 스택의 top이 현재 인덱스보다 작은 경우, 현재 인덱스보다 큰 것들은 모두 pop

스택에 push조건: 현재 인덱스

 

그렇다면 733번에서도 pop먼저 하고 push하면 될 것 같다

pop 조건: 없음(그냥 있기만 하면 뽑아라)
push 조건: 색깔을 바꾼 것들만 

 

2트

        static public int[][] FloodFill(int[][] image, int sr, int sc, int color)
        {
            int temp = image[sr][sc];   /// 기존의 값 저장
            image[sr][sc] = color;      // 새로운 값 갱신

            int row = image.Length;
            int col = image[0].Length;

            // DFS로 바꾸었다
            // 84번에서 배열의 인덱스를 스택에 저장했던 기억이 있다
            // 여기에서도 그렇게 해보자
            Stack<(int, int)> stack = new Stack<(int, int)>();
            // 84번 풀때 스택에 더이상 남아있는 인덱스가 없어질때까지 반복했다
            // 저번처럼
            // 중심점의 상하좌우를 조사할때, 각 4개에 대해 진행
            // pop 조건: 색깔이 바뀐 것들의 인덱스만 추가
            // push 조건: 색깔을 바꾼 것들만 

            // 먼저 맨 처음의 중심점을 넣고 시작한다
            stack.Push((sr, sc));

            while (stack.Count > 0)
            {
                (int r, int c) = stack.Pop();   ///
                image[r][c] = color;
                // 중심점(r,c)의 상하좌우를 모두 조사한다
                if (r - 1 >= 0 && (image[r - 1][c] == temp)) // 왼쪽 
                {
                    stack.Push((r - 1, c)); /// 왼
                }
                if (r + 1 < image.Length && (image[r + 1][c] == temp))
                {
                    stack.Push((r + 1, c)); /// 오른
                }
                if (c - 1 >= 0 && (image[r][c - 1] == temp))
                {
                    stack.Push((r, c - 1)); /// 위
                }
                if (c + 1 < image[c].Length && (image[r][c + 1] == temp))
                {
                    stack.Push((r, c + 1)); /// 아래
                }
            }
            return image;
        }

 

이것도 결과는 똑같이 나오는데

 

아.. 예외처리가 빠졌다

그리고 while을 추가하면서 불필요한 반복문을 제거했다

 

3트 (최종)

        static public int[][] FloodFill(int[][] image, int sr, int sc, int color)
        {
            int temp = image[sr][sc];
            if (temp == color)
            {
                return image;   // 기존과 같으면 바로 리턴
            }
            int row = image.Length;
            int col = image[0].Length;

            Stack<(int, int)> stack = new Stack<(int, int)>();
            stack.Push((sr, sc));

            while (stack.Count > 0)
            {
                (int r, int c) = stack.Pop();
                // 유효한 범위 내에서 같은 색상인지 확인 후 변경
                if (r < 0 || r >= row || c < 0 || c >= col || image[r][c] != temp)
                {
                    continue;
                }
                image[r][c] = color;
                //
                stack.Push((r - 1, c)); /// 왼
                stack.Push((r + 1, c)); /// 오른
                stack.Push((r, c - 1)); /// 위
                stack.Push((r, c + 1)); /// 아래
            }
            return image;
        }

 

 

 

 

difficulty : ★★