[프로그래머스 LV 2] 카카오프렌즈 컬러링북 C++

programmers.co.kr/learn/courses/30/lessons/1829?language=cpp

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

 

자바스크립트 알고리즘을 연습할라고 했는데..

C++로 풀고나니 자바스크립트는 아예 고를수도 없게 되어있었다

미리확인할껄...

 

전형적인 DFS/BFS문제이다.

DFS가 조금 더 편해서 이걸로풀었다.

 

 

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool visit[101][101];
 
int dfs(int m , int n , vector<vector<int>> picture ,int a, int b) {
    visit[a][b] = true;
    int cnt = 1;    
 
    for (int i = 0; i < 4; i++) {
        int x = a + dx[i];
        int y = b + dy[i];
 
        if (x >= m || y >= n || x < 0 || y < 0) continue;
        if (picture[x][y] == picture[a][b] && !visit[x][y]) {
            cnt+=dfs(m, n, picture, x, y);
        }
    }
    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;
 
    memset(visit, 0, sizeof(visit));
 
    for(int i=0 ; i<m ; i++)
        for (int j = 0; j < n; j++) {
            if (picture[i][j] != 0 && !visit[i][j]) {                
                max_size_of_one_area = max(max_size_of_one_area,dfs(m, n, picture, i, j));
                number_of_area++;
            }
        }
 
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}