[알고리즘C++]카카오프렌즈 컬러링북

오늘의 문제

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

카카오프렌즈 컬러링북

나의 풀이

#include <vector>
#include <iostream>

using namespace std;
bool visit[101][101]; // 방문?
int dfs(int m, int n, vector<vector<int>> picture, int target);

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            visit[i][j] = false;
        }
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(picture[i][j] != 0 && visit[i][j] == false){
                number_of_area++;
                max_size_of_one_area = max(max_size_of_one_area,dfs(i, j, picture, picture[i][j]));
            }
        }
    }

    vector<int> answer(2);
    answer[0] = number_of_area; // 몇개의 영역
    answer[1] = max_size_of_one_area; // 가장 큰 넓이
    return answer;
}

int dfs(int m, int n, vector<vector<int>> picture, int target){
    int result = 0;
    if(m>=0 && n>=0 && m < picture.size() && n < picture.size() && visit[m][n] == false && picture[m][n] == target){
        visit[m][n] = true; // 방문
        //cout<<m<<"/"<<n<<"방문"<<endl;
        result++;
        result += dfs(m+1, n, picture, target);
        result += dfs(m, n+1, picture, target);
        result += dfs(m-1, n, picture, target);
        result += dfs(m, n-1, picture, target);
        return result;
    }else{
        return 0;
    }   
}

모범 정답

#include <vector>
#include <algorithm>

using namespace std;

int M, N;
vector<vector<bool>> visited;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int dfs(int y, int x, vector<vector<int>>& picture)
{
  visited[y][x] = true;

  int ret = 1;
  for (int i = 0; i < 4; i++)
  {
    int cy = y + dy[i];
    int cx = x + dx[i];

    if (cy < 0 || cy >= N || cx < 0 || cx >= M ||
      visited[cy][cx] ||
      picture[cy][cx] != picture[y][x])
    {
      continue;
    }

    ret += dfs(cy, cx, picture);
  }
  return ret;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture)
{
  int number_of_area = 0;
  int max_size_of_one_area = 0;

  M = m;
  N = n;
  visited.assign(n, vector<bool>(m, false));

  for (int y = 0; y < n; y++)
  {
    for (int x = 0; x < m; x++)
    {
      if (picture[y][x] > 0 && !visited[y][x])
      {
        max_size_of_one_area = max(max_size_of_one_area, dfs(y, x, picture));
        number_of_area++;
      }
    }
  }

  vector<int> answer(2);
  answer[0] = number_of_area;
  answer[1] = max_size_of_one_area;
  return answer;
}

배운 점

• 나는 수기로 적었는데, 연산을 배열로 정의해서 사용하는것이 인상적이다.
• dfs를 이용해서 푸는것을 알자마자 슥 풀었다. 뿌듯해!!