[프로그래머스] 카카오컬러링북
문제요약
- 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;
}
Author And Source
이 문제에 관하여([프로그래머스] 카카오컬러링북), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@coding3392/프로그래머스-카카오컬러링북저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)