[프로그래머스] 카카오컬러링북

문제요약

• 2차원 컬러링북 도안이 주어집니다.
• 색칠을 해야하는 연결된 공간의 개수와
• 색칠을 하는 연결된 공간 중에 가장 큰 component의 영역 크기를 구하세요.

아이디어

seed를 뽑아가면서 bfs를 수행한다.

seed 추출 방법

그냥 도안을 쭉 돌면서 미방문&색깔이 있는 곳이면 반환하는 식

고칠점

색칠을 하지 않는 공간도 영역으로 칠지 혼동

색칠하지 않는 공간은 영역으로 치면 안된다.
그것은 테케를 봤을 때 2개의 영역만이 있다는 것을 보면 쉽게 알 수 있었는데
중간에 이를 망각하고 틀린 원인을 빈공간을 집계를 안 해서 그런가? 라고 생각해서 소스를 완전히 고쳤었다.

배열 초기화를 안함

쓰레기 값이 있는 배열을 그대로 사용했다... 앞으론 그냥 명시적으로 for문 돌면서 명시적으로 초기화를 해야겠다.

int visited[100][100] = {0,};

이렇게 하긴 했지만 이건 효과가 없었다.
코딩팁에 추가할 예정!

소스코드

#include <vector>
#include<queue>
#include<math.h>
#include<iostream>
using namespace std;
struct pos{
    int i, j;
};
vector<vector<int>> pic;
int m,n;
int visited[100][100]={0,};
pos get_seed(){
    for(int i = 0;i<m;i++){
        for(int j = 0;j<n;j++){
            if(visited[i][j] == 0 &&pic[i][j] !=0){
                return pos{i,j};
            }
        }
    }
    return pos{-1,-1};
}
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
bool inbox(pos p){
    return p.i>=0&&p.i<m&&p.j>=0&&p.j<n;
}

int bfs(pos p){
    int t = pic[p.i][p.j];
    queue<pos> q;
    q.push(p);
    visited[p.i][p.j] = t;
    int num = 1;
    while(!q.empty()){
        p = q.front();
        q.pop();
        
        for(int k = 0;k<4;k++){
            pos c = pos{p.i+di[k],p.j+dj[k]};
            if(inbox(c)&&pic[c.i][c.j] == t&&visited[c.i][c.j] ==0){
                q.push(c);
                visited[c.i][c.j] = t;
                num++;
            }
        }
    }
    //print_visited();
    return num;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int mm, int nn, vector<vector<int>> picture) {
    pic = picture;
    m = mm;n =nn;
    for(int i = 0;i<m;i++){
        for(int j =0;j<n;j++){
            visited[i][j] = 0;
        }
    }
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    pos seed = get_seed();
    while(seed.i!=-1){
        number_of_area++;
        max_size_of_one_area = max(max_size_of_one_area,bfs(seed));
        seed = get_seed();
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}