[프로그래머스] 카카오 프렌즈 컬러링북 (2017 카카오코드 예선)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829

 

<전체적 알고리즘>

단순 bfs문제이다.

1. 이차원 배열을 하나씩 순차 탐색한다.

2. 순차 탐색할 때 방문하지 않았고 색칠되어 있는 장소마다 bfs를 돌려준다.

3. bfs를 돌릴 때 queue에 들어간 개수를 카운팅해 영역의 크기를 max_area와 비교해 나간다.

3. bfs돌린 횟수가 결국 색칠한 영역의 개수이고 max_area(코드에서는maxx)가 제일 큰 영역의 크기이다.

 

<실수할 만한 점>

1. 원소가 0인 부분은 색칠이 되어 있지 않은 부분이다. 색칠 되어 있지 않은 부분은 영역으로 치지 않는다.

 

<전체 코드>

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

bool check[102][102];
int n,m;
vector<vector<int>> picture;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

int bfs(int startx, int starty)
{
	queue<pair<int, int>> q;
	check[startx][starty] = true;
	q.push(make_pair(startx, starty));
	int color = picture[startx][starty];
	int count = 0;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		count++;

		for (int d = 0; d < 4; d++)
		{
			int nextx = x + dir[d][0];
			int nexty = y + dir[d][1];
			if (nextx < 0 || nexty < 0 || nextx >= m || nexty >= n)continue;
			if (picture[nextx][nexty] != color)continue;
			if (check[nextx][nexty])continue;
			check[nextx][nexty] = true;

			q.push(make_pair(nextx, nexty));
		}
	}
	return count;
}


// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int mm, int nn, vector<vector<int>> pictures) {
   
    picture=pictures;  //전역변수 초기화
    n=nn;              //전역변수 초기화
    m=mm;              //전역변수 초기화   
    fill(&check[0][0],&check[99][100],0);  //전역변수 초기화  
    
    int area_count = 0;
	int maxx_area = 0;
    
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (check[i][j]||picture[i][j]==0)continue;  //방문한 적 있거나 색칠안되어 있으면 스킵
			
			maxx_area = max(maxx_area, bfs(i, j));
			area_count++;		
		}
	}
    
    vector<int> answer(2);
    answer[0] = area_count;
    answer[1] = maxx_area;
    return answer;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.