프로그래머스 - lv2 카카오프렌즈 컬러링북

카카오프렌즈 컬러링북

문제는 프로그래머스에서 확인 할 수 있다.

✔ 접근방법

1. BFS를 이용한 접근
2. 중복 좌표를 탐색하지 않도록 처리하는 것이 중요

✔ 첫 작성 코드

BFS문제라고 생각하지 못하고, 반복문을 이용하여 좌표들을 탐색하고 같은 색상별로 그룹을 만드는 풀이를 생각했다.
문제에 주어진 테스트들은 통과했지만, 제출하였을때 히든테스트케이스에서 에러가 발생했었다.

// 프로그래머스 컬러링북
// BFS 문제이나 반복문으로 풀어버린 문제..
#include <vector>
#include <iostream>

using namespace std;

vector<pair<int, vector<pair<int, int>>>> group;

void addGroup(int x, int y, vector<vector<int>> picture){
    int color = picture[x][y];
    vector<pair<int, int>> temp;
    bool check=false;
    vector<int> check_idx;
    if( group.empty() ){
        temp.push_back(make_pair(x,y));
        group.push_back(make_pair(color, temp));
    }
    else{
        for(int i=0, group_size=group.size(); i<group_size; i++){
            pair<int, vector<pair<int, int>>>& selected_group = group[i];
            int selected_color = selected_group.first;
            vector<pair<int,int>>& arr = selected_group.second;
            if( color == selected_color ){
                for(int j=0, arr_size=arr.size(); j<arr_size; j++){
                    if( arr[j].first == x-1 && arr[j].second == y){
                        if( !check ){
                          arr.push_back(make_pair(x,y));
                        }
                        check = true;
                        check_idx.push_back(i);
                        break;
                    }
                    // else if( arr[j].first == x && arr[j].second == y+1){
                    //    if( !check ){
                    //       arr.push_back(make_pair(x,y));
                    //     }
                    //     check = true;
                    //     check_idx.push_back(i);
                    //     break;
                    // }
                    // else if( arr[j].first == x+1 && arr[j].second == y){
                    //     if( !check ){
                    //       arr.push_back(make_pair(x,y));
                    //     }
                    //     check = true;
                    //     check_idx.push_back(i);
                    //     break;
                    // }
                    else if( arr[j].first == x && arr[j].second == y-1){
                        if( !check ){
                          arr.push_back(make_pair(x,y));
                        }
                        check = true;
                        check_idx.push_back(i);
                        break;
                    }
                }
            }
        }
        // 새로운 그룹 생성
        if(!check){
          temp.push_back(make_pair(x, y));
          group.push_back(make_pair(color, temp));
        }
        // 반복문 진행방향으로 인해 그룹에 추가되지 못한 케이스 처리
        // 0101
        // 1101
        // 0111
        // 의 경우 그룹이 나눠져 있게되는데, 이를 하나의 그룹으로 합쳐준다.
        else if(check && check_idx.size()==2){
          pair<int,int> tmp_pos;
          for(int i=0, size=group[check_idx[1]].second.size(); i<size; i++){
            tmp_pos = group[check_idx[1]].second[i];
            group[check_idx[0]].second.push_back(tmp_pos);
          }
          group.erase(group.begin()+check_idx[1]);
          check_idx.clear();
        }
    }
}

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

    for( int i=0; i<m; i++){
        for ( int j=0; j<n; j++){
            if( picture[i][j] != 0 ){
                addGroup(i, j, picture);
            }
        }
    }
    
    number_of_area = group.size();
    for(int i=0; i<group.size(); i++){
        if(max_size_of_one_area < (group[i].second).size() ){
            max_size_of_one_area = (group[i].second).size();
        }
    }

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

int main(void){
    int m=7;
    int n=7;
    vector<vector<int>> picture = {{0,1,1,0,1,0,0},
                                    {0,1,1,0,1,0,1},
                                    {1,1,1,0,1,0,1},
                                    {0,0,0,0,1,1,1},
                                    {0,1,0,0,0,0,0},
                                    {0,1,1,1,1,1,0},
                                    {0,1,1,1,0,0,0}};
    vector<int> ret;

    ret = solution( m, n, picture);

    cout << ret[0] << " " << ret[1] << endl;

    for(int i=0; i<group.size(); i++){
        cout << "color : " << group[i].first << endl;
        for( int j=0; j<(group[i].second).size(); j++){
            cout << "(" << (group[i].second)[j].first << " " << (group[i].second)[j].second << ") ";
        }
        cout << endl;
    }

    return 0;
}

✔ 수정된 코드

이후, BFS로 문제를 접근했고 BFS를 통해 노드를 재방문 하지않고 문제를 해결하는 방식을 취하니 히든테스트케이스와 실행시간에서도 문제없이 해결되었다.

// 프로그래머스 컬러링북
// BFS를 이용한 제대로 된 풀이.
// picture 에서 주변에 있는 같은 색을 한번에 탐색할때 BFS 사용
#include <vector>
#include <iostream>
#include <queue>
#include <unistd.h>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    queue<pair<int,int>> q;
    int cnt=0;
    int color=0;
    int cx[4] = {0,0,1,-1};
    int cy[4] = {1,-1,0,0};
    int pos_x, pos_y;
    int size_of_one_area[10001] = {0,};

    // 미방문 픽셀은 -로 체크
    for( int i=0; i<m; i++ ){
        for( int j=0; j<n; j++){
            picture[i][j] = -picture[i][j];
        }
    }

    for( int i=0; i<m; i++ ){
        for( int j=0; j<n; j++){
            pos_x = i;
            pos_y = j;
            if( picture[i][j] < 0 ){
                cnt++;
                // cout << cnt << endl;
                q.push(make_pair(i,j));
                color = -picture[i][j];
                picture[i][j] = cnt;
                while( !q.empty() ){
                    // cout << q.front().first << " " << q.front().second << " " << endl;
                    q.pop();
                    for(int k=0; k<4; k++){
                        if( pos_x+cx[k]>=0 && pos_x+cx[k]<m && pos_y+cy[k]>=0 && pos_y+cy[k]<n ){
                            if( color == -picture[pos_x+cx[k]][pos_y+cy[k]] ){
                                q.push(make_pair(pos_x+cx[k], pos_y+cy[k])); // 상하좌우에 있는 같은 색의 좌표를 큐에 추가함
                                picture[pos_x+cx[k]][pos_y+cy[k]] = cnt;    // 방문노드를 표시
                                // cout << "check " << pos_x+cx[k] << " " << pos_y+cy[k] << endl;
                            }
                        }
                    }
                    pos_x = q.front().first;
                    pos_y = q.front().second;
                }
            }
        }
    }

    number_of_area = cnt;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if( picture[i][j] != 0 ){
                size_of_one_area[picture[i][j]]++;
                if( max_size_of_one_area < size_of_one_area[picture[i][j]]){
                    max_size_of_one_area = size_of_one_area[picture[i][j]];
                }
            }
        }
    }

    // for(int i=0; i<m; i++){
    //     for(int j=0; j<n; j++){
    //         cout << picture[i][j];
    //     }
    //     cout << endl;
    // }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

int main(void){
    int m=7;
    int n=7;
    vector<vector<int>> picture = {{0,1,1,0,1,0,0},
                                    {0,1,1,0,1,0,1},
                                    {1,1,1,0,1,0,1},
                                    {0,0,0,0,1,1,1},
                                    {0,1,0,0,0,0,0},
                                    {0,1,1,1,1,1,0},
                                    {0,1,1,1,0,0,0}};
    
    vector<int> ret;

    ret = solution( m, n, picture);

    cout << ret[0] << " " << ret[1] << endl;

    return 0;
}

👍 참고 사이트

• 프로그래머스