[LeetCode] Flood Fill

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

Flood Fill - LeetCode

행렬에서 내가 선택한 값과 주변의 값들이 같을 경우 모두 newColor로 바꿔줘야 하는 문제 

 

즉 아래 예시에서 내가 고른 값(1,1)은 1이다. 주변의 1들은 모두 2로 바뀌어야 한다는 것이다. 

대신 대각선으로는 이동할 수 없고, 주변의 값이 다른 경우도 물론 이동할 수 없다. 

Flood Fill

즉 뿌리 뻗듯이 주변의 값들을 탐색하고 조건에 맞다면 이동 한 후 값을 변경해주면 되는 것이다. 

 

문제 분류는 DFS로 되어있으나 BFS를 이용해도 무방할 것 같다. 

우선 프로세스를 보자. 

 

1. 내가 선택한 index의 값을 target에 저장한다. 

2. target과 newColor과 같은 경우 주어진 배열을 바로 반환한다. 

   : 위 경우에서 2로 바꾸는게 아니라 1로 바꾸는 것이라면 아무리 바꿔도 원배열과 같기에 의미가 없다. 

3. 내가 선택한 Index의 값을 newColor로 바꿔준다. 

4. 선택한 index를 기준으로 유효한 인접 index를 구한다.

    4-1. up, down, left, right를 구하는데 행렬(mxn)의 크기를 고려해줘야 한다. 

5. DFS 고고 

   5-1 방문 여부는 newColor로 변경되면서 자동적으로 체크된다. 

6. 시작점을 기준으로 출발한다. 

 

바로 코드로 가보자!

 

class Solution {
    func floodFill(_ image: [[Int]], _ sr: Int, _ sc: Int, _ newColor: Int) -> [[Int]] {
        // 열
        let m = image[0].count
        // 행
        let n = image.count
        // 변경된 값을 적용해 줄 배열
        var result = image
        // 타겟값 (= 주변이 이 값과 같다면 바꿀 대상이 됨)
        let target = image[sr][sc]
        
        // 내가 선택한 값과 바꿔야 할 값이 같다면, 그냥 그대로 반환
        if target == newColor {
            return image
        }
        
        // 먼저 선택한 값은 바꿔준다. 
        result[sr][sc] = newColor
        
        func DFS(_ start: [Int]) {
            // 방문할 (i,j)
            var nextVisit = [[Int]]()
            nextVisit.append(start)
        
            while !nextVisit.isEmpty {
                let next = nextVisit.removeLast()
                // 인접 (up,down,left,right) 원소들 나열
                for adj in findAdj(next,m,n) {
                    // 그 값이 target과 같을 때
                    if result[adj[0]][adj[1]] == target {
                        // 값을 변경해주고
                        result[adj[0]][adj[1]] = newColor
                        // 다음에 방문할 배열에 넣어준다. 
                        nextVisit.append(adj)
                    }
                }
            }
        }
        // 시작점 
        DFS([sr,sc])
        
        return result
    }
    
    // 대각선 제외 인접(up,down,left,right) index들을 구한다.
    func findAdj(_ coor: [Int],_ m: Int, _ n: Int) -> [[Int]] {
            var res = [[Int]]()
            var x = coor[0]
            var y = coor[1]
            let u = [x,y-1]
            let d = [x,y+1]
            let l = [x-1, y]
            let r = [x+1,y]
            
            let dir = [u,d,l,r]
            for d in dir {
                // index 범위에 충족한다면 추가
                if (d[0] >= 0 && d[0] < n) && (d[1] >= 0 && d[1] < m) {
                    res.append(d)
                }
            }
            return res
        }
}

 

기본적인 DFS 문제! 왜인지 findAdj를 구할 때 조금 더 버벅였다...조급하게 풀어서 그런가 싶지만...!

DFS 문제를 풀 수록 점점 더 이해도가 높아지는 것 같다!

원리는 같은데 환경과 조건이 조금씩 다른 느낌...?

 

아무튼 끄읕

(tree형태의 DFS/BFS/Graph도 풀어봐야하는데.. 쉬운 것 부터 봐야겠다!)