[알고리즘] c++ cpp 카카오 프렌즈 컬러링 북

포인트 

1. BFS 너비 우선 탐색 (최대 넓이, 영역의 수, ~ )

 

#include <vector>
#include <queue>
#include <tuple>

using namespace std;

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

// 전형적인 BFS 문제
int bfs(int a, int b, int m, int n, vector<vector<int>> map)
{
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    visited[a][b] = true;
    int color = map[a][b];
    int cnt = 1;

    while (!q.empty())
    {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= m || ny >= n)
                continue;

            if (map[nx][ny] == color && !visited[nx][ny])
            {
                cnt++;
                visited[nx][ny] = true;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return cnt; // 방의 넓이를 나타냄
}

vector<int> solution(int m, int n, vector<vector<int>> picture)
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            visited[i][j] = false;
        }
    } //input

    int room = 0;
    int value = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (picture[i][j] != 0 && visited[i][j] == false)
            {
                room++;                                       // 영역의 수를 나타냄
                value = max(value, bfs(i, j, m, n, picture)); // 최대값을 구하는 문제
            }
        }
    }

    vector<int> answer = {room, value};
    return answer;
}