카카오프렌즈 컬러링 북 C++

문제설명

 

예제 입출력

m       n       picture                                                                                                                                                       answer

6

4

[[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]

[4, 5]

예제에 대한 설명

예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다.

 

 

 

#include <vector>
#include <iostream>
#include <algorithm> 
#include <cstring>

using namespace std;

int arr[101][101];
int UpDownLeftRight [4][2] ={{1,0},{-1,0},{0,1},{0,-1} };
vector<vector<int>> pic;
int M,N;

int dfs(int x,int y, int cnt )//x는 행 Y는 열
{
    
    arr[x][y]=true;
    
    for(int i=0; i<4;i++)
    {    
        int nextX = x + UpDownLeftRight[i][0];
        int nextY = y + UpDownLeftRight[i][1];
        
        if(nextX<0||nextX>=M|nextY<0||nextY>=N) continue;
        
        if(pic[x][y]==pic[nextX][nextY] && arr[nextX][nextY]==false)
        {
            cnt = dfs(nextX, nextY, cnt+1);            
        }
    }
    return cnt;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    pic = picture;
    M=m;N=n;
    
    memset(arr,0,sizeof(arr));
    
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(!arr[i][j] && picture[i][j] !=0)
            {
                number_of_area++;
                max_size_of_one_area = max(max_size_of_one_area,dfs(i,j,1));
            }
        }
    }
        
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

 

=> DFS나 BFS를 사용하여 풀어야 하는 문제였습니다. 

=> picture를 탐색시작하며 해당 값이 0이 아닐 경우부터 해당 값을 가지고 있는 상하좌우의 경우를 확인하였습니다.(DFS)

=> 이를 통해 첫 번째 값이 1일 경우, 1로 이루어진 구역의 모든 부분을 체크합니다. 

=> 이후, 체크되지 않은 부분을 탐색하며 다시 0이 아닌 경우를 확인하여 DFS를 재실행합니다. 

**코딩하며 틀린 부분 : UpDownLeftRight를 더해야 하는데 바보같이 arr의 값을 더하고 있었습니다. 

***BFS로도 풀어보겠습니다.