LeetCode 733(Flood Fill, java)

0. 문제

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

Flood Fill - LeetCode

 

 

1. 문제 설명

- 문제에서 이중 배열(image)과 시작점이 되는 row(= sr)와 column(= sc) 위치, 새로운 색상(= newColor)이 주어진다.

- 문제에서 제공하는 시작 위치의 값과 시작 위치를 기준으로 4방향에 존재하는 요소의 값이 동일하다면,

   해당 요소의 값을 newColor로 대체하는 것이 문제의 핵심이다.

 

- 이 문제는 재귀 함수에 대한 기본적인 이해가 있다면 충분히 해결할 수 있는 문제다.   

 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 시작점의 값을 판단해야 한다.

- 만약 시작점의 값이 newColor와 동일하다면 다른 요소의 값을 변경할 이유가 없다.

- 이미 newColor로 이루어진 이중 배열이기 때문이다. 

 

 

b) 두 번째 접근

- 만약 시작 위치의 값이 newColor와 다르다면, 시작 위치의 값(= startColor)을 저장한다.

- 만약 시작 위치를 기준으로 4방향에 위치한 요소가 startColor와 동일하다면, 해당 요소의 값을 newColor로 대체한다.

 

- 시작 위치를 기준으로 4방향에 위치한 각 요소의 4방향에 위치한 또 다른 요소들까지 검사한다.

- 즉, 시작 위치를 기준으로 배열의 모든 값을 비교하는 것이다. 

 

- 이처럼 반복적인 연산을, 적용 대상을 확장하는 형태의 문제는 재귀를 사용하여 풀어야 한다.

 

 

c) 세 번째 접근

- 재귀 함수의 움직임을 생각해보자.

- 시작 요소를 기준으로 4방향의 요소의 값이 startColor와 동일한지 검사한다. 

- 그러므로 더 이상 검사할 요소가 없을 때까지, 재귀는 4방향의 요소에 대한 검증을 반복해야 한다.

 

- 다음 코드를 보면서 이해해보자. 

 

 

3. 정답 코드

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if(image[sr][sc] == newColor) {
            return image;
        }
        
        int startColor = image[sr][sc];
        
        fill(image, sr, sc, startColor, newColor);
        return image;
    }
    
    public void fill(int[][] image, int sr, int sc, int startColor, int newColor) {
        if(sr < 0 || sc < 0 || sr >= image.length || 
             sc >= image[0].length || image[sr][sc] != startColor) { // 더 이상 검증할 수 없을 때
            return;
        }
        
        image[sr][sc] = newColor;
        
        fill(image, sr - 1, sc, startColor, newColor);
        fill(image, sr + 1, sc, startColor, newColor);
        fill(image, sr, sc - 1, startColor, newColor);
        fill(image, sr, sc + 1, startColor, newColor);
    }
}