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

 기본적인 그래프 탐색 문제이다. 각 좌표에서 그래프 탐색 후 방문체크를 한다. bfs를 해도되지만 각 타일에서 다음 타일과 비교해야하는 부분도 있으니 dfs로 풀이했다. 그러나 bfs로 풀이해도 문제없다.

유사한 문제 - https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

#include <vector>

using namespace std;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int M;
int N;
int area = 0;

bool visited[101][101];
int boad[101][101];

int cnt = 0;

void dfs(int hereX, int hereY){
    visited[hereX][hereY] = true;

    for(int i = 0; i < 4; i++){
        int nextX = hereX + dx[i];
        int nextY = hereY + dy[i];
        if(nextX < M && nextX > -1 && nextY < N && nextY > -1 && visited[nextX][nextY] == false && 
          boad[nextX][nextY] == boad[hereX][hereY]){
            visited[nextX][nextY] = true;
            cnt++;
            dfs(nextX, nextY);
        }
    }
}

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

 

 테캐가 1개인건 또 처음본다.