[leetcode] 733. Flood Fill

문제

---

풀이

주어진 2차원 배열에서 상하좌우 4방향으로 시작위치의 색과 같은 색이면 새로운 색으로 칠하면 되는 문제이다.

dfs, bfs 풀이로 풀면 된다.

 

처음에 아래와 같이 작성했다가 Time Limit Exceeded 나왔다.

class Solution {

    fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, newColor: Int): Array<IntArray> {
        val baseColor = image[sr][sc]

        fun fill(row: Int, col: Int) {
            if (row !in image.indices || col !in image[0].indices || image[row][col] != baseColor) {
                return
            }

            image[row][col] = newColor
            intArrayOf(-1, 1).forEach {
                fill(row + it, col)
                fill(row, col + it)
            }
        }
        fill(sr, sc)


        return image
    }
}

주어진 배열이 아래와 같고 시작위치가 [1][1] 이고 newColor 가 1인 경우다.

시작위치 [1][1]를 newColor인 1로 바꾸고 [1][2]로 가서 1로 바꾸고 다시 [1][1]로 오고를 무한 반복한다.

즉, 탐색해야하는 곳의 색이 newColor와 같아도 방문해서 Time Limit Exceeded 이 나왔다.

 

---

코드

class Solution {

    fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, newColor: Int): Array<IntArray> {
        val baseColor = image[sr][sc]

        fun fill(row: Int, col: Int) {
            if (row !in image.indices || col !in image[0].indices
                || image[row][col] != baseColor || image[row][col] == newColor
            ) {
                return
            }



            image[row][col] = newColor
            intArrayOf(-1, 1).forEach {
                fill(row + it, col)
                fill(row, col + it)
            }
        }
        fill(sr, sc)


        return image
    }
}

---

참고

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