[프로그래머스][Lv. 2] 카카오프렌즈 컬러링북 C++ 풀이

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

2017 카카오코드 예선에 나온 문제입니다.

 

풀이는 추후에 차차 올리도록 하겠습니다...

 

 

 

#include <vector>
#include <cstring>
#include <iostream>
 
using namespace std;
 
int width = 0, height = 0;
int** checked = NULL;
//  0: CHECKED ALREADY OR DIFFERENT COLOR
//  1: SAME REGION
int checkRegion(int i, int j, vector<vector<int>>& picture, int color) {
    if (i < 0 || i == height || j < 0 || j == width) { return 0; }
    if (checked[i][j] == 1 || color != picture[i][j] || picture[i][j] == 0) { return 0; }
    
    int curColor = picture[i][j], count = 1;
    checked[i][j] = 1;
    
    count += checkRegion(i - 1, j, picture, curColor); // U
    count += checkRegion(i, j - 1, picture, curColor); // L
    count += checkRegion(i, j + 1, picture, curColor); // R
    count += checkRegion(i + 1, j, picture, curColor); // D
    return count;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int regions = 0, maxSum = 0;
    width = n, height = m;
    checked = (int**)malloc(sizeof(int*) * height);
    
    for (int i = 0; i < height; i++) {
        *(checked + i) = (int*)malloc(sizeof(int) * width);
        memset(*(checked + i), 0, sizeof(int) * width);
    }
 
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (checked[i][j] == 0 && picture[i][j] > 0) {
                regions++;
                int count = checkRegion(i, j, picture, picture[i][j]);
                if (maxSum < count) {
                    maxSum = count;
                }
            }
        }
    }
    
    for (int i = 0; i < height; i++) {
        free(*(checked + i));
    }
    free(checked);
    
    vector<int> answer(2);
    answer[0] = regions;
    answer[1] = maxSum;
    return answer;
}