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

 

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

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

 

#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100
using namespace std;

bool visited[MAX][MAX];

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

int bfs(int y, int x, int m, int n, vector<vector<int>>& picture){      //한 영역씩
    int size=1;
    int num=picture[y][x];
    queue<pair<int,int>> q;
    q.push(make_pair(y,x));
    visited[y][x]=true;
    while (!q.empty()){
        int cy=q.front().first;
        int cx=q.front().second;
        q.pop();
        for (int i=0; i<4; i++){
            int ny=cy+dy[i];
            int nx=cx+dx[i];
            if (ny<0 || nx<0 || ny>=m || nx>=n){
                continue;
            }
            if (!visited[ny][nx] && picture[ny][nx]==num){
                visited[ny][nx]=true;
                size++;
                q.push(make_pair(ny,nx));
            }
        }
    }
    return size;
}

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<MAX; i++){
        for (int j=0; j<MAX; j++){
            visited[i][j]=false;
        }
    }
    for (int i=0; i<m; i++){
        for (int j=0; j<n; j++){
            if (!visited[i][j] && picture[i][j]!=0){
                number_of_area++;
                int size=bfs(i,j,m,n,picture);
                if (size>max_size_of_one_area){
                    max_size_of_one_area=size;
                }
            }
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

BFS 로 영역을 탐색하는 문제.

 

미방문 영역 && 0이 아닌 곳을 탐색한다.

탐색할 때는 한 영역씩 탐색한다. 즉, 상하좌우에 있고 && 아직 미방문 상태이고 && 숫자가 같은 애들을 방문하면서 탐색한다.

탐색이 끝난 후에는 탐색한 애들의 수를 리턴하고, 최대값을 갱신해준다.

한 영역씩 탐색할 때마다 영역++ 해주면 된다.