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

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

프로그래머스

 

풀이과정

bfs의 가장 기본적인 문제이다.  
가장 큰 영역을 구하고 몇 개의 영역이 있는지 리턴하면 되는 문제이다.

 

#include <vector>
#include <queue>

using namespace std;

int c[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int bfs(int x, int y, vector<vector<int>> picture, int num){
    queue<pair<int, int>> q;
    q.push({x, y});
    c[x][y] = 1;

    int cnt = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        cnt++;

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx > picture.size() - 1 || ny < 0 || ny > picture[0].size() - 1)
                continue;
            if(picture[nx][ny] == num && !c[nx][ny]){
                q.push({nx, ny});
                c[nx][ny] = 1;
            }
        }
    }
    return cnt;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector<int> answer(2);
    for(int i = 0; i < picture.size(); i++){
        for(int j = 0; j < picture[i].size(); j++){
            c[i][j] = 0;
        }
    }
    int max = 0, area = 0;
    for(int i = 0; i < picture.size(); i++){
        for(int j = 0; j < picture[i].size(); j++){
            if(picture[i][j] != 0 && !c[i][j]){
                int res = bfs(i, j, picture, picture[i][j]);
                if(max < res) max = res;
                area++;
            }
        }
    }
    answer[0] = area;
    answer[1] = max;
    return answer;
}