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

https://school.programmers.co.kr/learn/courses/30/lessons/1829?language=cpp 

프로그래머스

전체 코드 (1) - picture를 arr 2차원 배열로 옮겨 품 ( 사실 picture로만으로도 충분함 )

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    int arr[101][101];
    bool visit[101][101];
    int side[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    for(int i=0;i<picture.size();i++)
    {
        for(int j=0;j<picture[i].size();j++)
        {
            arr[i][j]=picture[i][j];
            visit[i][j]=false;
        }
    }
    
    queue<pair<int,int>> q;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(visit[i][j]==false&&arr[i][j]!=0)
            {
                number_of_area++;
                int area=1;
                q.push(make_pair(i,j));
                visit[i][j]=true;
                while(!q.empty())
                {
                    int y=q.front().first; int x=q.front().second;
                    q.pop();
                    for(int k=0;k<4;k++)
                    {
                        int ny=y+side[k][0];
                        int nx=x+side[k][1];
                        if(ny>=0&&nx>=0&&ny<m&&nx<n&&visit[ny][nx]==false
                          &&arr[y][x]==arr[ny][nx])
                        {
                            visit[ny][nx]=true;
                            q.push(make_pair(ny,nx));
                            area++;
                        }
                    }
                    
                }
                max_size_of_one_area=max(max_size_of_one_area,area);
                
            }
        }
    }
     
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

전체 코드 (2) - picture로만 품

#include <vector>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    bool visit[101][101];
    int side[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    fill(&visit[0][0],&visit[100][101],false);
    
    queue<pair<int,int>> q;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(visit[i][j]==false&&picture[i][j]!=0)
            {
                number_of_area++;
                int area=1;
                q.push(make_pair(i,j));
                visit[i][j]=true;
                while(!q.empty())
                {
                    int y=q.front().first; int x=q.front().second;
                    q.pop();
                    for(int k=0;k<4;k++)
                    {
                        int ny=y+side[k][0];
                        int nx=x+side[k][1];
                        if(ny>=0&&nx>=0&&ny<m&&nx<n&&visit[ny][nx]==false
                          &&picture[y][x]==picture[ny][nx])
                        {
                            visit[ny][nx]=true;
                            q.push(make_pair(ny,nx));
                            area++;
                        }
                    }
                    
                }
                max_size_of_one_area=max(max_size_of_one_area,area);
                
            }
        }
    }

    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

 

BFS로 풀었다.

간단히 visit를 통해서 처음 방문한 공간이라면 새로 방문한 영역으로 영역의 개수 number_of_area를 +1 해준다.

이후 이 새로운 영역을 중심으로 같은 번호인 영역을 방문한다. 이떄 변수 area를 통해 영역 넓이를 계산한다.

그리고 max_size_of_one_area와 비교해 영역이 더 넓다면 갱신해준다.

상하좌우 이동은 size 2차원 배열을 통해 이동한다.