[C++] 카카오 프렌즈 컬러링북 (Lv.2)

문제 (level2, 2017 카카오코드 예선)

문제바로가기

프로그래머스

---

풀이

BFS,DFS 두 가지 방법으로 풀 수 있는데,

저는 재귀함수를 이용한 DFS를 사용해 풀었습니다.

#include <vector>
using namespace std;

int count;
int temp_area;
int max_area;
bool** visited; //해당 칸 검사체크용
int G_m;
int G_n;



void check(int row,int col,vector<vector<int>>& picture)
{
    visited[row][col]=true;
    temp_area++;
    if(col-1>=0 && picture[row][col]!=0 && picture[row][col]==picture[row][col-1] && visited[row][col-1]==false) //왼쪽으로 감
    {
        check(row,col-1,picture);
    }
    
     if(col+1<G_n && picture[row][col]!=0 && picture[row][col]==picture[row][col+1] && visited[row][col+1]==false) //오른쪽으로 감
    {
        check(row,col+1,picture);
    }
    
     if(row+1<G_m && picture[row][col]!=0 && picture[row][col]==picture[row+1][col] && visited[row+1][col]==false) //아래로 감
    {
        check(row+1,col,picture);
    }
    
     if(row-1>=0 && picture[row-1][col]!=0 && picture[row][col]==picture[row-1][col] && visited[row-1][col]==false) //위로 감
    {
        check(row-1,col,picture);
    }
    
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    count=0;
    temp_area=0;
    max_area=0;
    G_m=m;
    G_n=n;
    
    visited=new bool*[m+5];
    for(int i = 0; i < m; i++) 
    {
        visited[i] = new bool[n+5];
        fill_n(visited[i],n,false);
    }

    
    for(int row=0; row<m; row++)
    {
        for(int col=0; col<n; col++)
        {
            if(picture[row][col]!=0 && visited[row][col]==false)
            {
                check(row,col,picture);
                count++;
            }
            
            if(temp_area>max_area)
                max_area=temp_area;
            
            temp_area=0;
        }
    }
    
    
    vector<int> aws;
    aws.push_back(count);
    aws.push_back(max_area);
    
    return aws;
}

 

핵심은 check()함수입니다.

check함수는 어떤 한 칸을 기준으로, 해당 칸과 같은 영역인 곳을 검사해주는 함수입니다. 

영역의 크기(칸의 갯수)를 이 함수 속에서 구합니다. (temp_area와 max_area 전역변수를 이용함) 

 

해당 함수는 DFS를 구현한 함수입니다. 

인자로 row,col,picture 을 받습니다. 

 

이때 이중 for문을 사용해서 check()함수를 실행해주는데, 

함수 실행 조건은

 

1.  해당 칸에 색칠이 되어있어야함. (=0이 아니여야함)
2.  아직 방문하지 않은 칸이여야함.

 

이 조건을 만족할때만 check함수를 실행시켜줍니다.

그리고 check함수를 빠져나오면 count++를 해주는데,

count변수는 영역의 갯수를 저장하는 전역변수입니다. 

 

그럼, check함수는 해당칸을 기준으로

상하좌우를 검사합니다.

 

검사하여서 같은 색이라면 재귀적으로 해당 칸으로 움직인다음 다시 

check함수를 실행시킵니다. 

이 과정에서 방문한 칸은 visited[row][col]=true; 처리를 하여서 방문했음을 처리해줍니다.

그리고 temp_area++;를 해주어서 현재 검사중인 영역이 몇칸인지도 같이 기록합니다. 

 

영역 검사가 모두 끝났다면 max_area보다 temp_area가 더 크다면,

max_area=temp_area;

로 최대 영역의 크기를 업데이트 해줍니다.

 

 

 

 

이렇게 2중 for문이 모두 끝났다면, 

영역의 갯수인 count와 최대 영역의 칸의 갯수인 max_area를 

vector변수에 push_back해주고 return 해줍니다.