카카오프렌즈 컬러링북 (feat. 프로그래머스, 1829번)

카카오프렌즈 컬러링북
https://programmers.co.kr/learn/courses/30/lessons/1829

프로그래머스

반응형

// woohyeon.kim
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int M, N, connected_point_count;
bool check[101][101];
vector<pair<int, int>> move_points;

inline void dfs(const int& m_index, const int& n_index, const vector<vector<int>>& picture)
{
    check[m_index][n_index] = true;
    ++connected_point_count;
    for(const auto& move_point : move_points)
    {
        auto row_index = m_index + move_point.first;
        auto column_index = n_index + move_point.second;
        if((0 <= row_index) && (row_index < M) &&
           (0 <= column_index) && (column_index < N) &&
           !check[row_index][column_index] &&
           (picture[m_index][n_index] == picture[row_index][column_index]))
            dfs(row_index, column_index, picture);
    }
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    M = m;
    N = n;
    connected_point_count = 0;
    fill(&check[0][0], &check[M][N], false);
    move_points.push_back(make_pair(0, 1));
    move_points.push_back(make_pair(0, -1));
    move_points.push_back(make_pair(1, 0));
    move_points.push_back(make_pair(-1, 0));
    
    vector<int> connected_point_tmpl;
    for(auto row = 0; row < m; ++row)
    {
        for(auto column = 0; column < n; ++column)
        {
            if(picture[row][column] && !check[row][column])
            {
                connected_point_count = 0;
                dfs(row, column, picture);
                connected_point_tmpl.push_back(connected_point_count);
            }
        }
    }
    return vector<int>{static_cast<int>(connected_point_tmpl.size()), *max_element(connected_point_tmpl.begin(), connected_point_tmpl.end())};
}
// *&)*@*

[0,0]에서 시작된다고 봤을때, 한 칸씩 이동하며([0,1] [0,-1] [1,0] [-1,0]) [0,0]과 같은 값을 가지는지를 확인하는 문제입니다.

여기서 한 칸씩 이동이라는게 포인트인데, [0, 0]에서 [0,1]을 봤더니 같은 값이라면 다음은 [0,2]를 보는 방식입니다. (세균맨 같은 형태로)

또한 재귀다보니 [0,0]에서 상하좌우를 체크한 뒤에 다음 스탭으로 가는게 아니라

체크된 위치부터 다시 상하좌우가 시작되는 형태가 됩니다.

​

connected_point_tmpl에는 결국 연결됨의 순서별 연결 개수가 담기게 됩니다.

궁금하신점 있으시면 알려드릴께요!