카카오프렌즈 컬러링북

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

 

 

그냥 bfs 기초 탐색 문제이다.

 

딱히 풀이는.. 없고 bfs 돌리면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct POINT {
	int y, x;
};
int m, n;
vector<vector<int>> picture;
int number_of_area = 0;
int max_size_of_one_area = 0;
int visited[101][101];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

void bfs(int u, int v) {
	
	queue<POINT> q;
	visited[u][v] = 1;
	q.push({ u,v });
	int candi = 1;

	while (!q.empty()) {
		POINT cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			POINT next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];

			if (next.y < 0 || next.y >= m || next.x < 0 || next.x >= n) continue;

			if (picture[cur.y][cur.x] == picture[next.y][next.x] && visited[next.y][next.x] == 0) {
				candi += 1;
				visited[next.y][next.x] = 1;
				q.push(next);
			}
		}
	}
	if (candi > max_size_of_one_area) max_size_of_one_area = candi;
}

int main(void) {

	m = 6, n = 4;
	picture = {
		{ 1, 1, 1, 0 },
		{ 1, 2, 2, 0 },
		{ 1, 0, 0, 1 },
		{ 0, 0, 0, 1 },
		{ 0, 0, 0, 3 },
		{ 0, 0, 0, 3 } };


	for (int y = 0; y < m; y++) {
		for (int x = 0; x < n; x++) {
			if (visited[y][x] == 0 && picture[y][x] != 0) {
				number_of_area += 1;
				bfs(y, x);
			}
		}
	}

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

	getchar();
	getchar();

	return 0;
}