[프로그래머스] 레벨 2 - 카카오프렌즈 컬러링북 (2017 카카오코드 예선)

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

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

전형적인 BFS 탐색 문제다.

영역별로 영역의 크기를 구해주고 벡터에 저장한 뒤 마지막에 내림차순 정렬로 [0]번째 요소가 가장 큰 면적임을 저장해주면 된다.

 

아래는 소스코드

#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int cnt = 0;
bool check[100][100];
void falsing(){
    for(int i=0; i<100; i++)
        for(int j=0; j<100; j++)
            check[i][j] = false;
}
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    falsing();
    
    vector<int> areas;
    for(int r=0; r<m; r++){
        for(int c=0; c<n; c++){
            if(picture[r][c] != 0 && !check[r][c]){
                int curcolor = picture[r][c];
                cnt++;
                check[r][c] = true;
                queue<pair<int, int> > q;
                q.push(make_pair(r, c));
                while(!q.empty()){
                    int fr = q.front().first;
                    int fc = q.front().second;
                    q.pop();
                    for(int i=0; i<4; i++){
                        int nr = fr + direction[i].dr;
                        int nc = fc + direction[i].dc;
                        if(nr >= 0 && nr < m && nc >= 0 && nc < n){
                            if(!check[nr][nc] && picture[nr][nc] == curcolor){
                                check[nr][nc] = true;
                                q.push(make_pair(nr, nc));
                                cnt++;
                            }
                        }
                    }
                }
                areas.push_back(cnt);
                cnt = 0;
            }            
        }
    }    
    sort(areas.begin(), areas.end(), greater<int>());
    answer[0] = areas.size();
    answer[1] = areas[0];
    return answer;
}