[Easy] 733. Flood Fill (아마존 / 구글 코딩 테스트 기출 문제)

#문제 설명

Leetcode 733번문제는 2d 배열에 x와y, 즉, 시작점이 주어지고, 정수 color가 주어진다. 이 주어진 배열의 시작점에서 시작해 그 지점에서 왼쪽, 오른쪽, 위, 아래의 지점이 시작한 color와 같다면, 그 지점의 color를 주어진 새로운 color로 바꾸는 문제이다. 예를 들어 위에 사진의 2d배열에서 시작점이 가운데 즉 (1,1)이라고 가정하면, 시작점을 주어진 새로운 color 2로 바꾸고, 처음 시작점에서 위 (0,1)로가면 시작점과 같은 color 1이기 때문에 2로 바꾼다, 또 (0,1)의 왼쪽과 오른쪽모두 1이기 때문에 2로 바꾼다. 이 과정을 계속 반복하면 된다. 

#문제 풀이

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
         //시작점의 color와 새로운 color가 같은면 기존의 주어진 2d 배열 반환
    	//시작점의 color와 새로운 컬러가 같을때 infinite recursion,즉, stackoverflow가 방지
        if(image[sr][sc] == color){
            return image;
        }
        //2d배열을 돌아다니면서 color를 바꿔주는 private helper-function 호출
        fill(image, sr,sc, image[sr][sc], color);
	//바뀐 2d 배열 반환
        return image;
    }
    //사실상 이번 문제를 풀어주는 helper-function
    private void fill(int[][] image, int sr, int sc, int oldColor, int newColor) {
    	//sr과 sc (즉 x,y)의 indexOutOfBound 방지 및, 현재 좌표가 시작점의 color와 같지 않을시 
        //아무것도 반환하지 않음
        if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != oldColor){
            return;
        }
        //현재좌표를 새로운 color로 바꿔줌
        image[sr][sc] = newColor;
		
        //2d 배열을 traverse함
        
        //sr - 1, 즉 row - 1 이기때문에 아래로 한칸 이동
        fill(image , sr - 1, sc ,oldColor, newColor);
        //sr + 1, 즉, row + 1 이기때문에 위로 한칸 이동
        fill(image , sr + 1, sc ,oldColor, newColor);
        //sc - 1, 즉, column - 1 이기때문에 왼쪽으로 한칸 이동
        fill(image , sr, sc - 1 ,oldColor, newColor);
        //sc + 1, 즉, column + 1 이기때문에 오른쪽으로 한칸 이동
        fill(image , sr, sc + 1 ,oldColor, newColor);
    }
}

 

#다른 풀이

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int color = image[sr][sc];
        if (color != newColor) dfs(image, sr, sc, color, newColor);
        return image;
    }
    public void dfs(int[][] image, int r, int c, int color, int newColor) {
        if (image[r][c] == color) {
            image[r][c] = newColor;
            if (r >= 1) dfs(image, r-1, c, color, newColor);
            if (c >= 1) dfs(image, r, c-1, color, newColor);
            if (r+1 < image.length) dfs(image, r+1, c, color, newColor);
            if (c+1 < image[0].length) dfs(image, r, c+1, color, newColor);
        }
    }
}

위 답과 비슷하게 DFS 함수를 사용한 풀이 이다.