[Programmers] 카카오프렌즈 컬러링북

컬러링북의 영역의 개수와 최대 영역의 크기를 구하는 문제이다.

문제해결전략
컬러링북의 모든 좌표에서 bfs를 사용하여 현재 좌표의 색과 일치하는 색을 찾아 개수를 얻어내고, bfs가 몇번 일어났는지 확인하면 된다.

세부적으로 살펴보면 모든 좌표에 대하여 만약 해당 좌표에서의 색이 0이라면 그냥 넘어가고, 이미 방문했던 좌표여도 그냥 넘어간다.

둘 다 아니면 해당 좌표에서 bfs를 하는데, 이것의 의미는 해당 영역이 존재하는 의미이므로 영역의 개수를 추가해 준다.

bfs과정은 상하좌우를 살펴 이미 방문한 적이 있거나, 범위를 벗어나거나, 영역의 색과 일치하지 않으면 그냥 넘어가고 세 경우 다 아니라면 방문을 하는 것이다.

전형적인 bfs 문제였다.

코드

#include <vector>
#include <queue>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector<int> answer;
    int xp[4] = {-1,1,0,0};
    int yp[4] = {0,0,-1,1};
    
    int visited[101][101];
    for(int i=0;i<picture.size();i++){
        for(int j=0;j<picture[i].size();j++){
            visited[i][j] = 0;
        }
    }

    int ma = -1;
    int tmp = 0;
    for(int i=0;i<picture.size();i++){
        for(int j=0;j<picture[i].size();j++){
            if(visited[i][j] != 0)
                continue;
            if(picture[i][j] == 0)
                continue;
            visited[i][j] = 1;
            int cnt = 1;
            tmp++;
            queue<pair<pair<int,int>,int>> q;
            q.push(make_pair(make_pair(i,j),picture[i][j]));
            while(!q.empty()){
                int x = q.front().first.first;
                int y = q.front().first.second;
                int z = q.front().second;
                q.pop();
                for(int k=0;k<4;k++){
                    int xx = x + xp[k];
                    int yy = y + yp[k];
                    if(xx < 0 || xx >= m || yy < 0 || yy >= n)
                        continue;
                    if(visited[xx][yy] != 0)
                        continue;
                    if(picture[xx][yy] != z)
                        continue;
                    q.push(make_pair(make_pair(xx,yy),z));
                    visited[xx][yy] = 1;
                    cnt++;
                }
            }
            ma = max(ma,cnt);
        }
    }
    answer.push_back(tmp);
    answer.push_back(ma);
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/1829