[DFS 단순 반복] 프로그래머스 카카오프렌즈 컬러링북 C++

 

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

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

#include <vector>
#include <iostream>

using namespace std;

int num = 0;
bool** visited; // [] 사용X

void dfs(int m, int n, vector<vector<int>> picture, bool** visited, int x, int y)
{
    visited[y][x] = true;
    num++;
    //cout << x <<" " << y << " " << num << "\n";
    if (x < n-1)
    {
        if ((!visited[y][x+1]) && (picture[y][x] == picture[y][x+1]))
        {
            dfs(m, n, picture, visited, x+1, y);
        }
    }
    
    if (x > 0)
    {
        if ((!visited[y][x-1]) && (picture[y][x] == picture[y][x-1]))
        {
            dfs(m, n, picture, visited, x-1, y);
        }
    }
    
    if (y > 0)
    {
        if ((!visited[y-1][x]) && (picture[y][x] == picture[y-1][x]))
        {
            dfs(m, n, picture, visited, x, y-1);
        }
    }
    
    if (y < m-1)
    {
        if ((!visited[y+1][x]) && (picture[y][x] == picture[y+1][x]))
        {
            dfs(m, n, picture, visited, x, y+1);
        }
    }
    
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    visited = new bool* [m]; // [] 사용X
    
    for (int i = 0; i < m; i++)
    {
        visited[i] = new bool[n];
        for (int j = 0; j < n; j++)
        {
            visited[i][j] = false;
        }
        cout << "\n";
    }
    
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if ((!visited[i][j]) && (picture[i][j] != 0)) {
                number_of_area++;
                dfs(m, n, picture, visited, j, i);
                if (num > max_size_of_one_area) max_size_of_one_area = num;
                num = 0; // 위치
            }
        }
    }

    vector<int> answer(2, 0);
    answer = {number_of_area, max_size_of_one_area};
    return answer;
}