[프로그래머스] 프로그래머스 Level2 카카오프렌즈 컬러링북 C++ (카카오 코딩테스트)

문제

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

코딩테스트 연습 - 카카오프렌즈 컬러링북

풀이

BFS를 통해 해결할 수 있었다. 모든 좌표에 대해 BFS를 돌며 최대 크기와 영역의 개수를 구해주면 되고, 인접한 칸의 조건이 상하좌우뿐만 아니라 같은 색상의 공간임을 잘 활용하여 BFS를 돌기전에 색상 값을 미리 지정해두고 탐색을 하면서 그 색상과 일치하는 좌표를 Queue에 넣어주면 된다.

코드

#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;

const int dx[4] = { 1, 0, -1 ,0 };
const int dy[4] = { 0, 1, 0, -1 };
bool visited[101][101];

int bfs(int i, int j, int m, int n, vector<vector<int>> board)
{
    int color = board[i][j];
    queue<pair<int, int>> q;
    q.push({i, j});
    visited[i][j] = true;
    int size = 0;

    while (!q.empty())
    {
        auto cur = q.front();
        size++;
        q.pop();

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

            if (nx < 0 || nx >= m || ny < 0 || ny >= n)
            {
                continue;
            }
            if (visited[nx][ny] || board[nx][ny] != color)
            {
                continue;
            }
           
            q.push({ nx, ny });
            visited[nx][ny] = true;
        }
    }

    return size;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {

    int number_of_area = 0;
    int max_size_of_one_area = 0;

    memset(visited, false, sizeof(visited));

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!visited[i][j] && picture[i][j] != 0)
            {
                max_size_of_one_area = max(max_size_of_one_area, bfs(i, j, m, n, picture));
                number_of_area++;
            }
        }
    }

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