프로그래머스 - 카카오프렌즈 컬러링 북 - C++

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

프로그래머스

 

#include <vector>

using namespace std;

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

bool CheckPos(int x,int y,int m,int n)
{
    if(x>=0 && x<m && y>=0 && y<n)
        return true;
    else return false;
}

void DFS(vector<vector<int>>& board,
         vector<vector<bool>>& ch,int x,int y,int type,int& cnt,int m,int n)
{
    for(int i=0;i<4;i++)
    {
        if(CheckPos(x+dx[i],y+dy[i],m,n)&&ch[x+dx[i]][y+dy[i]]==false&&
          board[x+dx[i]][y+dy[i]]==type)
        {
            ch[x+dx[i]][y+dy[i]]=true;
            board[x+dx[i]][y+dy[i]]=0;
            DFS(board,ch,x+dx[i],y+dy[i],type,++cnt,m,n);
        }
    }
}

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++)
        {
            if(picture[i][j]!=0)
            {
                vector<vector<bool>> ch(m,vector<bool>(n));
                int cnt=0;
                DFS(picture,ch,i,j,picture[i][j],cnt,m,n);
                number_of_area++;
                if(max_size_of_one_area<cnt)max_size_of_one_area=cnt;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

문제에서 주어진 2차원배열에서 각 영역을 판단하여 몇개의 영역이 있는지와 영역 중 가장 큰 영역의 크기는 얼마인지를 구하는 문제이다.

 

영역을 판단해야한다는 부분에서 바로 dfs를 떠올렸다. 

 

간단하게 재귀함수로 구현했으며 주어진 2차원 배열 자체에서 0이 아닌 원소가 나왔을 때 그 좌표를 기준으로 DFS를 시작한다. 

이 때, 한 번 계산한 영역은 0으로 처리한다. 

따라서 main에서 2중 반복문을 돌며 0이 아닐 때 DFS를 시작하면 새로운 영역마다 DFS를 시작할 수 있다. 

 

for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(picture[i][j]!=0)
            {
                vector<vector<bool>> ch(m,vector<bool>(n));
                int cnt=0;
                DFS(picture,ch,i,j,picture[i][j],cnt,m,n);
                number_of_area++;
                if(max_size_of_one_area<cnt)max_size_of_one_area=cnt;
            }
        }
    }

main의 2중 반복문이다. 

새로운 영역이 나왔을 때 DFS가 시작되므로 바로 영역수를 1카운트한다. 

그리고 cnt를 매개변수로 넘겨서 종료 후 영역크기를 알 수 있게한다. 

따라서 max보다 크면 업데이트한다.

 

void DFS(vector<vector<int>>& board,
         vector<vector<bool>>& ch,int x,int y,int type,int& cnt,int m,int n)
{
    for(int i=0;i<4;i++)
    {
        if(CheckPos(x+dx[i],y+dy[i],m,n)&&ch[x+dx[i]][y+dy[i]]==false&&
          board[x+dx[i]][y+dy[i]]==type)
        {
            ch[x+dx[i]][y+dy[i]]=true;
            board[x+dx[i]][y+dy[i]]=0;
            DFS(board,ch,x+dx[i],y+dy[i],type,++cnt,m,n);
        }
    }
}

DFS 함수이다. 재귀로 구현했다.

매개변수는 board 와 ch 는 각각 주어진 2차원 배열과 방문한 노드인지를 판단할 2차원 배열이다.

x,y는 dfs 동작에서 현재 기준이 될 좌표이다. 

즉, x,y 를 기준으로 상하좌우로 뻗어나가는 dfs동작을 진행한다. 

type 은 어떤 영역에 대해서 dfs중인지 구분하기 위함이다. 

cnt는 영역의 크기를 판단할 변수이다. 

m,n은 주어진 2차원 배열의 크기이다. 

 

for문으로 상하좌우를 체크하며 유효한 좌표인지 방문안한노드인지 type이 같은지를 체크하고 

전부 부합한다면 그 부분을 0으로 처리하며 방문한것으로 체크하고 DFS를 실행한다. 

 

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

bool CheckPos(int x,int y,int m,int n)
{
    if(x>=0 && x<m && y>=0 && y<n)
        return true;
    else return false;
}

마지막 checkpos 즉, 유효한 좌표인지 판단하는 함수와

dx,dy 배열은 dfs에서 for문으로 상하좌우 좌표를 간단히 표현하는 방법이다.