Intuition

4-directionally라는 문제 조건에 맞춰, 재귀함수를 상하좌우로 호출하면 될 것이라고 생각했다.

Approach

본격적으로 문제를 풀기에 앞서 2차원 배열을 반환하기 위한 세팅을 해줘야한다. 관련 설명은 [LeetCode] 77. Combinations에 기술했다.

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
//
#include <stdlib.h>
//
int imgSize;
int imgColSize;
int targetColor;
int originColor;
int** res;
...
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes) {
    imgSize=imageSize;
    imgColSize=*imageColSize;
    targetColor=color;
    originColor=image[sr][sc];
	//
    *returnSize=imageSize;
    *returnColumnSizes=(int*)malloc(sizeof(int)*imageSize);
    for (int i=0;i<imageSize;i++) (*returnColumnSizes)[i]=*imageColSize;
	//
    res=(int**)malloc(sizeof(int*)*imageSize);
    for (int i=0;i<imageSize;i++){
        res[i]=(int*)malloc(sizeof(int)*(*imageColSize));
        for (int j=0;j<(*imageColSize);j++) res[i][j]=image[i][j];
    } 
    ...
    return res;
}

특정 좌표에 문제에서 원하는 color로 색칠을 해주는 함수를 만들어준다.

void paint(int sr, int sc){
    res[sr][sc]=targetColor;
	...
}

이후 sequence는 상하좌우(순서무관)로 함수를 호출하면 되는데, 이때 호출조건은 다음과 같다.
1. grid의 밖으로 벗어나지 않아야 한다.
즉, column과 row의 값이 0이상이며 각각 columnSize와 rowSize보다 작아야한다.
2. 원래 color와 동일해야 한다.

함수를 호출할 때에는 상하좌우 각각을 code 네줄로 처리할 수도 있지만 아래와 같은 테크닉으로 한줄로 처리하는 것이 간편하다.

int xpos[4] = {1, 0, -1, 0};
int ypos[4] = {0, 1, 0, -1};
//
void paint(int sr, int sc){
    res[sr][sc]=targetColor;
...
    for(int i = 0; i < 4; i++) {
        int new_r = sr + ypos[i];
        int new_c = sc + xpos[i];
        if(new_r < imgSize && new_r >= 0 && new_c < imgColSize && new_c >= 0 && res[new_r][new_c]==originColor) paint(new_r, new_c);
    }
}

3. stackOverflow 및 불필요한 호출을 피하기 위해 한 번 방문한 grid는 다시 방문하지 않는다.

int xpos[4] = {1, 0, -1, 0};
int ypos[4] = {0, 1, 0, -1};
//
void paint(int sr, int sc){
    res[sr][sc]=targetColor;
    visited[sr][sc]=1; // visited 배열은 0으로 초기화 된 상태, 방문한 경우 1로 체크 
    for(int i = 0; i < 4; i++) {
        int new_r = sr + ypos[i];
        int new_c = sc + xpos[i];
        if(new_r < imgSize && new_r >= 0 && new_c < imgColSize && new_c >= 0 && !visited[new_r][new_c] && res[new_r][new_c]==originColor) paint(new_r, new_c); // visited 조건 추가
    }
}

Solution

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

#include <stdlib.h>

int imgSize;
int imgColSize;
int targetColor;
int originColor;
int** res;
int** visited;

int xpos[4] = {1, 0, -1, 0};
int ypos[4] = {0, 1, 0, -1};

void paint(int sr, int sc){
    res[sr][sc]=targetColor;
    visited[sr][sc]=1;
    for(int i = 0; i < 4; i++) {
        int new_r = sr + ypos[i];
        int new_c = sc + xpos[i];
        if(new_r < imgSize && new_r >= 0 && new_c < imgColSize && new_c >= 0 && !visited[new_r][new_c] && res[new_r][new_c]==originColor) paint(new_r, new_c);
    }
}

int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes) {
    imgSize=imageSize;
    imgColSize=*imageColSize;
    targetColor=color;
    originColor=image[sr][sc];

    *returnSize=imageSize;
    *returnColumnSizes=(int*)malloc(sizeof(int)*imageSize);
    for (int i=0;i<imageSize;i++) (*returnColumnSizes)[i]=*imageColSize;

    res=(int**)malloc(sizeof(int*)*imageSize);
    for (int i=0;i<imageSize;i++){
        res[i]=(int*)malloc(sizeof(int)*(*imageColSize));
        for (int j=0;j<(*imageColSize);j++) res[i][j]=image[i][j];
    } 

    visited=(int**)malloc(sizeof(int*)*imageSize);
    for (int i=0;i<imageSize;i++){
        visited[i]=(int*)malloc(sizeof(int)*(*imageColSize));
        for (int j=0;j<(*imageColSize);j++) visited[i][j]=0;
    } 

    paint(sr,sc);

    return res;
}

Time Complexity

visited 여부와 color에 따라 그때그때 함수 호출횟수가 변경되서 정확한 시간복잡도 계산은 해내지 못했다. 매우 Rough하게 매번 상하좌우를 체크하므로 $O(4^n)$

지적 및 질문 환영