카카오 프렌즈 컬러링북(2017 카카오코드 예선)

문제 링크

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

 

 

풀이

처음에 에러 처리를 위해 양 사이드에 0을 추가하였고(컴퓨터 비전 과목에서 배웠던...)

그리고 BFS로 큐에 넣으면서 같은 number에 있는 것을 연결해주었다.

전역변수로 선언하지 않고 참조자(&)를 사용하여 해결하였다.

 

 

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int bfs(vector<vector<int>>& picture, int j, int i)
{
    const int color = picture[j][i];
    int area = 0;   // 영역 계산
    queue<pair<int, int>> q;
    q.push(make_pair(j, i));
    picture[j][i] = 0;
    
    // BFS start
    while(!q.empty())
    {
        area++;
        int frontJ = q.front().first;
        int frontI = q.front().second;
        q.pop();
        if(picture[frontJ-1][frontI] == color)
        {
            q.push(make_pair(frontJ-1, frontI));
            picture[frontJ-1][frontI] = 0;
        }
        if(picture[frontJ+1][frontI] == color)
        {
            q.push(make_pair(frontJ+1, frontI));
            picture[frontJ+1][frontI] = 0;
        }
        if(picture[frontJ][frontI-1] == color)
        {
            q.push(make_pair(frontJ, frontI-1));
            picture[frontJ][frontI-1] = 0;
        }
        if(picture[frontJ][frontI+1] == color)
        {
            q.push(make_pair(frontJ, frontI+1));
            picture[frontJ][frontI+1] = 0;
        }
    }
    return area;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    // Error 처리를 위해 0을 추가한다.
    vector<int> zeroVec;
    zeroVec.assign(n, 0);
    picture.insert(picture.begin(), zeroVec);
    picture.push_back(zeroVec);
    m+=2;
    n+=2;
    for(int j=0; j<m; j++)
    {
        picture[j].insert(picture[j].begin(), 0);
        picture[j].push_back(0);
    }

    // 검사
    for(int j = 1; j < m - 1; j++)
    {
        for(int i = 1; i < n - 1; i++)
        {
            if(picture[j][i] != 0)
            {
                number_of_area++;
                int bfsArea = bfs(picture, j, i);
                if(max_size_of_one_area < bfsArea)
                {
                    max_size_of_one_area = bfsArea;
                }
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}