[프로그래머스] 카카오 프렌즈 컬러링북

풀이)

bfs를 가지고 쉽게 풀 수 있는 문제이다.

모든 영역 좌표을 살피며, 

색깔이 0이 아니고 이전에 방문하지 않았던 곳(좌표)이면 bfs를 호출하여 같은 컬러를 가지고 있는 영역을 방문 표시 해주면 된다.

코드)

#include <vector>
#include <queue>
#include<iostream>
using namespace std;
bool visited[100][100];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

int bfs(int a,int b,int m,int n,vector<vector<int>>picture){
    queue <pair<int,int>> qu;
    qu.push({a,b});
    visited[a][b] = true;
    int cnt = 1;
    int color = picture[a][b];
    //cout << "c: " << color << endl;
    while(!qu.empty()){
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >=0 &&ny <m && nx >=0 && nx<n){
                if(visited[ny][nx] || picture[ny][nx] != color) continue;
                visited[ny][nx] = true;
                qu.push({ny,nx});
                cnt++;
            }
        }
    }
    return cnt;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
     for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            visited[i][j] = false;
        }
     }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(visited[i][j] == false && picture[i][j] > 0){
                int temp = bfs(i,j,m,n,picture);
                max_size_of_one_area =  max_size_of_one_area > temp? max_size_of_one_area:temp;
                number_of_area++;
            }
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    //cout << answer[0] << answer[1] << endl;
    return answer;
}