[프로그래머스] Level 2 : 카카오프렌즈 컬러링북

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

프로그래머스

 

전형적인 BFS 문제

1. 그림의 크기가 최대 100이니 100x100 방문 배열 선언 

2. 그림을 순회하며 방문을 안 했고, 0이 아니면 BFS 진입

3. 상하좌우 검사하며 같은 그림이 있으면 방문 체크, 넓이+1

4. BFS가 끝나면, 영역+1, 넓이는 max를 통해 기존값과 새 넓이를 비교해 최대 값 유지

 

주의해야 할 점 : 방문 배열을 전역 변수에 선언 시, 반드시 함수 내에서 초기화를 해줘야 함.     

#include <vector>
#include <queue>
using namespace std;

int dy[] = { 0, -1, 0, 1 };
int dx[] = { -1, 0, 1, 0 };
bool Visit[100][100];

void BFS(int Y, int X, int Color, vector<vector<int>>& Picture, int& Count)
{
	queue<int> qy, qx;
	qy.push(Y), qx.push(X);
	Visit[Y][X] = 1;

	while (!qy.empty() || !qx.empty())
	{
		int y = qy.front(), x = qx.front();
		qy.pop(), qx.pop();

		for (int i = 0; i < 4; ++i)
		{
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= Picture.size() || nx >= Picture[0].size() || Visit[ny][nx] || Picture[ny][nx] != Color) continue;

			Visit[ny][nx] = 1;
			qy.push(ny), qx.push(nx);
			Count++;
		}
	}
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
	int Area = 0, Extent = 0;
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			Visit[i][j] = 0;

	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (Visit[i][j] || !picture[i][j]) continue;

			int Count = 1;
			BFS(i, j, picture[i][j], picture, Count);
			Area++, Extent = max(Extent, Count);
		}
	}
	return { Area, Extent };
}