20231109_기록_Flood Fill(LeetCode 773)

오늘 한 것들

 

C# 문법 종합반 5주차 과제 2 - LeetCode 733. Flood Fill

 

오늘은 TIL은 LeetCode 733. Flood Fill의 풀이이다.

 

5주차 강의에서 여러가지 알고리즘을 배우면서 배웠던 DFS를 사용하라고 만든 문제이지만,

모든 풀이 및 해설들이 DFS를 사용하고 있기에

단순히 DFS를 사용해서는 해당 개념을 잘 이해하지 못할 것으로 판단하여

직접적으로 해당 문제를 고찰하며 풀이하려고 했다.

(그냥 DFS를 사용해서 풀고, DFS의 개념을 이해하는 것도 좋았을 것 같다)

 

우선은 문제의 해석인데

image라고 주어진 (m x n)의 행렬이 있다.

그 행렬의 m번째 행과 n번째 열에 있는 수는 image[m][n]으로 표현할 수 있다.

또한 integer가 3개 sr, sc, color가 주어지는데, sr은 시작점의 행을, sc는 시작점의 열을,

color는 해당 함수를 진행할 숫자값이다.

 

이제 Flood Fill을 수행하면,

초기에 주어진 image[sr][sc]의 위치로 가서 그 곳의 값 x을 가져온다.

그 후에 x를 color로 변환한 후에, 4방향(상하좌우)로 이동하며 x값과 같은 값이 있다면 color로 변환해준다.

만약 변환한 곳이 있다면 그 변환한 곳의 4방향도 체크해주며, 이를 반복한다.

변환한 곳과 그 곳과 연결된 4방향들을 모두 체크했다면 프로그램이 종료된다.

그 후에 변환된 값을 output으로 반환한다.

는 경우에 올바른 로직을 짜는 것이 문제이다.

 

 

이는 DFS를 사용하면 보다 쉽고 간편하게 코딩을 할 수 있는데,

기존의 image[sr][sc]의 값을 oldColor로 지정하고, 입력된 color 값이 oldColor값과 다르면,

DFS라는 함수를 실행하게 만들면 된다.

 

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) {
        int oldColor = image[sr][sc];
        if (oldColor != color) {
            DFS(image, sr, sc, oldColor, color);
        }
        return image;
    }

    private void DFS(int[][] image, int sr, int sc, int oldColor, int color) {
        if (sr < 0 || sr >= image.Length || sc < 0 || sc >= image[0].Length || image[sr][sc] != oldColor) {
            return;
        }

        image[sr][sc] = color;
        DFS(image, sr + 1, sc, oldColor, color);
        DFS(image, sr - 1, sc, oldColor, color);
        DFS(image, sr, sc + 1, oldColor, color);
        DFS(image, sr, sc - 1, oldColor, color);
    }
}

DFS라는 함수는 주어진 변수들과 oldColor를 대입한 후에

sr과 sc가 범위 내에 있고, 현재 셀이 이전의 셀과 같은 색상인지 확인한 후에

현재 셀에 색칠하고, 상하좌우로 로직을 반복한다.

 

DFS라는 개념을 이해하면 이해할 수 있는 사고의 진행방향이지만, 함수로 만드는 것은 쉽지 않다.

특히 재귀적으로 함수 내에서 특정 조건을 만족하면 빠져나오고,

그렇지 않으면 4방향으로 로직을 반복하게 만드는 것은 생각보다 쉽지 않았다.

 

 

따라서 보다 직관적이고 어렵지 않은 개념을 사용하여 문제 풀이에 도전했는데,

기본 로직의 흐름은

현재 좌표와 그 좌표와 인접한 한 칸을 비교하여 oldColor라면 color로 변환하는 작업을 수행하는데,

01. image[sr][sc]의 위치를 color 값으로 변경한다.

02. image[sr][sc]의 위치를 기준으로 오른쪽으로(sc++) 진행하며 같은 작업을 반복한다.

03. (sc > 0 인 경우에) image[sr][sc]의 위치를 기준으로 왼쪽으로(sc--) 진행하며 같은 작업을 반복한다.

04. image[sr][sc]의 위치를 기준으로 아래쪽으로(sr++) 진행하며 oldColor를 찾아서 color로 변경한다.

05. (sr > 0 인 경우에) image[sr][sc]의 위치를 기준으로 위쪽으로(sr--) 진행하며 같은 작업을 반복한다.

06. 0, 1, 2, ... , n-1 열에서 sr행을 기준으로 아래쪽, 위쪽으로 진행하며 같은 작업을 반복한다.

07. 0, 1, 2, ... , m-1 행에서 좌측에서 우측으로 진행하며 같은 작업을 반복한다.

08. 0, 1, 2, ... , n-1 열에서 위에서 아래로 진행하며 같은 작업을 반복한다.

09. 순서를 역으로 n-1, n-2, ... , 0열까지 아래에서 위로 진행하며 같은 작업을 반복한다.

10. 같은 방식으로 m-1, m-2, ... , 0행까지 오른쪽에서 왼쪽으로 진행하며 같은 작업을 반복한다.

 

이 로직의 흐름을 그림으로 정리하면 아래와 같다.

그림에는 빠져있는데,

8번의 경우 9의 역으로 위에서 아래로

10번의 경우 7의 역으로 오른쪽에서 왼쪽으로 판단 작업을 진행할 것이다.

 

 

위의 로직으로 구현한 코드는 아래와 같다.

 

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

        // m x n 의 행렬이 주어지고
        // sr, sc 가 주어지고 color의 숫자값이 주어진다
        // 해당 sr, sc의 위치에서 해당 위치의 숫자 값을
        // 상하좌우로 연결된 모든 color 값을 주어진 color 값으로 바꾼다.

        // for 문으로 sr, sc를 가지고 시작해서
        // sr에서 m까지 가면서 같은 숫자가 있는 곳까지만 이동하며 color 값으로 숫자 바꾸기
        // sr에서 0까지 가면서 같은 숫자가 있는 곳까지만 이동하며 color 값으로 숫자 바꾸기
        // sc에서 n까지 가면서 같은 숫자가 있는 곳까지만 이동하며 color 값으로 숫자 바꾸기
        // sc에서 0까지 가면서 같은 숫자가 있는 곳까지만 이동하며 color 값으로 숫자 바꾸기
        // 0에서 n 사이에서 sr 에서 작업 반복
        // 0부터 m까지 왼쪽에서 오른쪽(0부터 n까지) 작업 반복
        // m부터 0까지 오른쪽에서 왼쪽(n부터 0까지) 작업 반복 (위의 역순)


        int m = image.Length;
        int n = image[0].Length;
        int oldColor = image[sr][sc];
        if (oldColor == color) return image;
        int newColor = -1;
        image[sr][sc] = newColor;  // 초기에 주어진 위치의 color를 변경


        // sr행에서 오른쪽으로 조건에 맞는 경우 color로 변경
        for (int i = sc; i < n - 1; i++)
        {
            if(image[sr][i] == newColor && image[sr][i + 1] == oldColor)
            image[sr][i + 1] = newColor;
        }
        
        if (sc > 0)
        {
            // sr행에서 왼쪽으로 조건에 맞는 경우 color로 변경
            for (int i = sc; i >= 1; i--)
            {
                if(image[sr][i] == newColor && image[sr][i - 1] == oldColor)
                image[sr][i - 1] = newColor;
            }
        }


        // sc열에서 아래쪽으로 조건에 맞는 경우 color로 변경
        for (int i = sr; i < m - 1; i++)
        {
            if(image[i][sc] == newColor && image[i + 1][sc] == oldColor)
            image[i + 1][sc] = newColor;
        }
        
        if (sr > 0)
        {
            // sc열에서 위쪽으로 조건에 맞는 경우 color로 변경
            for (int i = sr; i >= 1; i--)
            {
                if(image[i][sc] == newColor && image[i - 1][sc] == oldColor)
                image[i - 1][sc] = newColor;
            }
        }
        
        // 0열 ~ n-1열에서 sr행을 기준으로 아래쪽, 위쪽으로 조건에 맞는 경우 color로 변경
        for (int j = 0; j <= n - 1; j++)
        {
            for (int i = sr; i < m - 1; i++)
            {
                if((image[i][j] == newColor) && (image[i + 1][j] == oldColor))
                image[i + 1][j] = newColor;
            }
            
            if (sr > 0)
            {
                for (int i = sr; i >= 1; i--)
                {
                    if((image[i][j] == newColor) && image[i - 1][j] == oldColor)
                    image[i - 1][j] = newColor;
                }
            }
        }

        // 0열 ~ n-1열을 좌측에서 오른쪽으로 + 0행 ~ m-1행까지 작업
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n - 1; j++)
            {
                if((image[i][j] == newColor) && (image[i][j + 1]) == oldColor)
                image[i][j + 1] = newColor;
            }
        }

        // 0 ~ m-1행을 위에서 아래로 + 0 ~ n-1열까지 작업
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m - 1; j++)
            {
                if((image[j][i] == newColor) && (image[j + 1][i]) == oldColor)
                image[j + 1][i] = newColor;
            }
        }

        // 위의 작업을 역으로 진행.
        // 아래에서 위로
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j > 0; j--)
            {
                if((image[j][i] == newColor) && (image[j - 1][i] == oldColor))
                image[j - 1][i] = newColor;
            }
        }

        // 오른쪽에서 왼쪽으로
        
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j > 0; j--)
            {
                if((image[i][j] == newColor) && (image[i][j - 1] == oldColor))
                image[i][j - 1] = newColor;
            }
        }

        for (int i = 0; i <= m - 1; i++)
        {
            for (int j = 0; j <= n - 1; j++)
            {
                if(image[i][j] == newColor)
                image[i][j] = color;
            }
        }

        return image;        
    }
}

 

이 코드를 구현하면서 가장 어려움을 겪었던 것은

조건문과 배열에서의 변수(i와 j)의 위치 혹은 사용법으로

조건문이 for (int i = 0; i < m; i++) 이라면

출력되는 값은 (0, 1, 2, 3, ... , m -1)으로 출력되는 것을 알고 있지만,

이를 m x n 배열에 응용하려고 하자

배열의 image[m][n]값은

image[0][0] image[0][1] ... image[0][n-2] image[0][n-1]

image[1][0] image[1][1] ... image[1][n-2] image[1][n-1]

...

image[m-2][0] image[m-2][1] ... image[m-2][n-2] image[m-2][n-1]

image[m-1][0] image[m-1][1] ... image[m-1][n-2] image[m-1][n-1]

의 구조로 첫 위치는 [0][0], 마지막 위치는 [m-1][n-1]로 표현해야되는데

조건문의 조건을 표시하는 과정에서 실수가 많이 나왔다.

 

 

이를 통해서 조건문과 배열, 행렬에 대해 근본적인 이해부터 돌아갔으며,

컴퓨터로만 이해하려고 하자 이해가 잘 되지 않아 공책에 표시하며 이를 이해했다.

이 과정에서 애매하게 자리잡고 있었던 개념들을 좀 더 체득할 수 있었다.

 

 

이후에는 생각하지 못했던 것들로 오류가 났던 것으로,

sr과 sc가 0인 경우에 3번과 5번이 작동되지 않았던 오류

(3번과 5번의 sr > 0, sc > 0인 조건은 이후에 추가했다)

 

color 값이 image[i][j]에 이미 존재하는 경우에 생기는 오류

-> 이는 문제에서 주어진 조건인 image[i][j]의 값이 0이상이라는 조건으로

newcolor라는 값을 -1로 대입하여 우선 로직을 진행한 후에,

해당 행렬에서 newcolor면 color 값을 대입하는 것으로 해결했다.

 

LeetCode에서 BFS를 사용하여 문제를 푼다면 쉽게 풀 수 있어서 Easy 난이도로 난이도를 책정한 것으로 추정되나

직접적으로 가까운 위치를 비교하며 색칠하는 로직으로 해결하려고하자 체감 난이도는 보다 높았다.

 

작업을 진행하면서 처음에 떠오른 내용은 현재 위치 값을 갖고 있으므로

현재 위치와 한 칸 옆의 위치를 비교하여 색칠해가는 방식을 채택하는건 어떨까라는 아이디어로 시작한 것으로,

주어진 위치의 상하좌우를 끝까지 칠하고,

주어진 위치의 가로열을 기준으로 상하로 끝까지 칠하고(혹은 세로열을 기준으로 좌우로 끝까지 칠하고)

그 후에 처음부터 끝까지 칠하는 방식으로 아이디어를 구체화하여 진행했다.

 

코딩 과정에서 행렬에 대한 잘못된 이해가 있었기에 반복문에서 변수 값을 지정하는데 문제가 있었고,

이를 행렬에 대입하다보니 System.IndexOutOfRangeException 가 계속 나타나 어려움을 겪었다.

이를 ChatGPT나 구글링으로 해결하는 것이 아니라

잘못 알고 있었던 개념들을 재확인하며 진행하여, 이후에 비슷한 문제를 만나더라도 해결할 수 있을 것 같다.

 

또, 아이디어가 좋았다고 생각되나 비어있던 부분이 있었는데,

sr과 sc가 0인 경우를 빠뜨리고 진행했던 점이나,

처음부터 끝까지 색칠하는 경우에 왼쪽에서 오른쪽으로 한 번. 아래에서 위으로 한 번 가면 충분할 것으로 생각하였는데,

이에 대한 반제가 나타나

왼쪽에서 오른쪽으로 한 번 간 후에 위에서 아래으로 한 번 진행하고

그 후에 아래에서 위로, 오른쪽에서 왼쪽으로 가는 과정을 거치며

전체적인 과정도 → ↓ ↑ ← 으로 진행하는 방식으로 개선했다.

 

 

원래는 오늘 5주차 과제를 마무리하고 오후부터는

Chapter 2 프로그래밍기초 개인과제

를 진행하려고 하였으나, 만만치 않은 문제에 만만치 않은 아이디어가 생각나서 이를 해결하는데 많은 시간을 소모하였다.

과제에 대해 진행이 되지 않은 점은 아쉽지만

오늘 이 문제를 해결하면서 잘못 알았던 개념들도 많이 재확인할 수 있었으며,

이렇게 문제를 끝까지 자신의 아이디어로 해결할 수 있어서 좋은 기회가 된 것으로 생각된다.