스파르타 내배캠 Unity 3기 12일차

마구마구 공부하기!

 

 

드디어 2번째 팀 프로젝트 주차에 들어왔다!

하지만 오늘의 TIL 주제는 알고리즘이다!

어제 쓴게 3번째 과제였는데 오늘은 2번째 과제를 봐야겠다(역순인 이유는 나도몰루다)

 

 

---

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

Flood Fill - LeetCode

 

 

해당 문제는 LeetCode 733번 문제이다.

 

문제 해석

이미지는 m x n 크기의 정수 그리드로 표현되며, image[i][j]는 이미지의 해당 픽셀 값을 나타냅니다.

또한 세 개의 정수 sr, sc, color가 주어집니다. 이미지[sr][sc] 픽셀에서 시작하여 이미지에 대해 플러드 필을 수행해야 합니다.

플러드 필을 수행하려면 시작 픽셀과 같은 색상의 4방향으로 연결된 모든 픽셀을 고려해야 합니다. 또한 해당 픽셀과 4방향으로 연결된 픽셀들의 색상도 동일하게 변경해야 합니다. 이 작업을 반복하여 계속 진행합니다. 변경된 이미지를 반환해야 합니다.

 

해당 문제의 솔루션 코드는 다음과 같이 쓸 수 있다.

 

enum Direction { Up, Left, Down, Right }

        static int[][] FloodFill(int[][] image, int sr, int sc, int color)
        {
            // 시작 좌표의 색이 칠해야 하는 색과 같으면 변화가 없으니 return
            if (image[sr][sc] == color)
                return image;            

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

            Coloring(image, sr, sc, originColor, color);

            return image;
        }

        static void Coloring(int[][] image, int startY, int startX, int originColor, int color)
        {
            // 방향을 정해줄 인덱스
            int index = 0;
            Direction dir;
            
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            // 해당 좌표에서 4방향 확인
            for (int i = 0; i < 4; i++)
            {
                int posY = startY;
                int posX = startX;

                // 0 ~ 3을 순환                
                dir = (Direction)(index % 4);
                index++;

                // 시작 좌표에서 dir 방향 배열 원소로 좌표 변경 
                posY += dirY[(int)dir];
                posX += dirX[(int)dir];

                // 이미지의 위치가 배열 밖이면 continue
                if (posY < 0 || posY >= image.Length || posX < 0 || posX >= image[posY].Length)
                    continue;
                // 해당 배열 원소가 원색(originColor)과 다르면 continue
                if (image[posY][posX] != originColor)
                    continue;                

                // 해당 배열 원소를 색칠
                image[posY][posX] = color;

                // 색칠 가능한 원소 좌표에서 4방향 검사를 해야하므로 재귀적 호출
                Coloring(image, posY, posX, originColor, color);
            }
        }

 

 

먼저 그림으로 어떤식으로 진행할지 알아보자.

 

예시1 을 기준으로

color 로 2가 주어졌고, image[1][1] 에서 시작한다고 했다.

image[1][1] 에서 시작하여 각 픽셀의 4방향에 대해

원래 image[1][1] 과 같은 색(1) 이었다면 모두 2 로 칠하는 룰이다.

 

 

만약 위쪽 방향을 먼저 칠했다고 가정하면, 북쪽은 image[1][1] 의 원색이었던 1과 같으니 2로 칠하고

 

마찬가지로 칠해진 픽셀 image[0][1]을 기준으로 4방향에 대해 칠해야 한다.

그렇다면 image[0][1] 의 좌우도 역시 원색인 1과 같으니 칠해주고

 

image[0][0] 의 아래인 image[1][0] 과 그 아래인 image[2][0] 역시 원색인 1과 같으니 칠해준다.

 

 

하지만 시작점이었던 image[1][1] 의 우측과 아래는 원색인 1과 다르기에

칠하지 않으며, 역시 그 위치에서 4방향에 대해 조사하지 않는다.

 

 

위 처럼 진행하며, 설명을 직관적으로 하기 위해 다소 생략된 부분을 이제 코드를 짚어가며 알아보자.

 

if (image[sr][sc] == color)
return image;

 

먼저 주어진 color의 값이 image[sr][sc]와 같다고 한다면 모든 방향에대해 아무 변화가 없을 것이다.

그러므로 바로 return 하도록 한다.

 

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

Coloring(image, sr, sc, originColor, color);

return image;

 

그 다음으로 시작 지점인 image[sr][sc]의 원색을 int originColor에 저장하도록 하자.

이는 다른 픽셀에서 비교하기 위함이다.

그 후 image[sr][sc] 를 주어진 color로 칠하고, Coloring 메서드로 모든 방향에 대해 조사하도록 하자.

 

enum Direction { Up, Left, Down, Right }


//Coloring 메서드
            // 방향을 정해줄 인덱스
            int index = 0;
            Direction dir;
            
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

 

먼저 조사할 방향을 Up부터 반시계 방향으로 (Left, Down, Right) 정한다. 이는 열거형을 통해 구분한다.

 

int[] dirY 와 int[] dirX 를 선언 해 이차원 배열인 image[][] 에 대해 좌표를 정할 수 있게 해주자.

좌표라고 하는 이유는 현재 예시의 image[][]를 좌표화 시키면

{

{1, 1, 1}

{1, 1, 0}

{1, 0, 1}

}

위처럼 표현할 수 있다.

또한 x는 -1, 1이 정방향이지만, y는 -1, 1이 역방향이므로 Up 일 때 -1이 되어야 한다.

// 해당 좌표에서 4방향 확인
            for (int i = 0; i < 4; i++)
            {
                int posY = startY;
                int posX = startX;

                // 0 ~ 3을 순환                
                dir = (Direction)(index % 4);
                index++;

                // 시작 좌표에서 dir 방향 배열 원소로 좌표 변경 
                posY += dirY[(int)dir];
                posX += dirX[(int)dir];

                // 이미지의 위치가 배열 밖이면 continue
                if (posY < 0 || posY >= image.Length || posX < 0 || posX >= image[posY].Length)
                    continue;
                // 해당 배열 원소가 원색(originColor)과 다르면 continue
                if (image[posY][posX] != originColor)
                    continue;                

                // 해당 배열 원소를 색칠
                image[posY][posX] = color;

                // 색칠 가능한 원소 좌표에서 4방향 검사를 해야하므로 재귀적 호출
                Coloring(image, posY, posX, originColor, color);
            }

 

for문을 통해 시작 좌표에서 4방향을 조사하므로 4번 반복한다.

 

시작 좌표에서 다음 좌표를 조사 할 때, 해당 좌표가 그리드 밖이면 continue

if(posY < 0 || posY >= image.Length || posX < 0 || posX >= image[posY].Length)

 

다음 좌표의 색이 originColor와 다르면 칠할 수 없으므로 continue

if (image[posY][posX] != originColor)

 

해당 조건을 통과하면 칠할 수 있으니 image[posY][posX] = color 로 칠하도록 하자.

 

그리고 다음 좌표가 칠할 수 있으면 그 좌표에서도 4방향에대해 조사해야하므로 재귀적 호출을 하고 이 때 시작 좌표를.

for문 처음에 설정한 좌표인 posY, posX를 매개변수로 전달한다.

 

재귀호출이 끝나면 index를 증가시켜 방향을 바꿔 다시 조사한다.

 

모든조사가 끝나게 되면 칠할 수 있는 영역은 모두 칠해진다.