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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1829

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

1. 주의할 점

- 같은 색일때에만 큐에 넣는다

 

2. 구현

- Check[][] 배열을 초기화한다

- Pictures[][] 배열에 대해 0이 아니고 확인하지 않은 곳이라면 BFS를 수행한다

- 4가지 방향 탐색을 하며 같은 색이고 방문하지 않았다면 Queue에 추가한다

 

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int y,x;
};
bool check[100][100]={false,};
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

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++)
            check[i][j]=false;
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            int val = picture[i][j];
            if(val==0 || check[i][j]) continue;
            queue<info> q;
            int cnt=1;
            check[i][j]=true;
            q.push({i,j});
            while(!q.empty()){
                int cy = q.front().y;
                int cx = q.front().x;
                q.pop();
                for(int k=0;k<4;k++){
                    int nx = cx+dx[k];
                    int ny = cy+dy[k];
                    if(nx>=0 && ny>=0 && nx<n && ny<m && picture[ny][nx]==val && !check[ny][nx]){
                        check[ny][nx]=true;
                        q.push({ny,nx});
                        cnt++;
                    }
                }
            }
            number_of_area++;
            max_size_of_one_area = max(max_size_of_one_area,cnt);
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}