[프로그래머스 2레벨] 카카오프렌즈 컬러링북 (C++)

#include <vector>
#include <cstring>

using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool visited[101][101];
int cnt;

void dfs(int m, int n, int x, int y, vector<vector<int>>& picture, int target)
{
    visited[x][y] = 1;    
    cnt++;
    for(int i=0; i<4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || ny < 0 || nx >=m || ny >=n) continue;
        if(visited[nx][ny] || picture[nx][ny] != target) continue;
        dfs(m, n, nx, ny, picture, target);
    }
    
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) { 
    vector<int> answer(2);
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(visited[i][j] || !picture[i][j]) continue;
            cnt = 0;
            dfs(m, n, i, j, picture, picture[i][j]);
            answer[0]++; //영역 개수
            answer[1] = max(answer[1], cnt); //최대 영역
        }
    }
    
    return answer;
}

 

생각보다 간단한 bfs or dfs 문제이다.

방문 배열에 추가적으로 piccutre 값 여부를 체크한다.

만약 picture 값이 존재하면 영역이 있다는 것이기에 해당 지점을 토대로 dfs를 돌려 연결된 값들을 체크한다.

4방향을 돌려가며 picture 값이 추가로 있는 지 체크하고, 있으면 추가 체크 없다면 종료한다.

이때 cnt 값 또한 따로 카운트하여 최대 영역 수를 체크하기 위한 용도로 사용한다.

단순하게 모든 범위에 대해 이를 반복해준다.