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

포인트

1. bfs를 잘 이해하고 있는가를 아는것이 중요한 것 같습니다. 이 문제는 같은 색깔인지까지 고려하는 모습을 볼 수 있습니다. 

2. bfs 도 유형이 여러가지가 있습니다. (최대 넓이, 영역의 개수 등등) 이해를 하면서 넘어갑시다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

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

using namespace std;

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

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]) {
                q.push(make_pair(nx, ny));
                cnt+=1;
                visited[nx][ny] = true;
            }
        }
    }
    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;
        }
    }

    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]) {
                value = max(value, bfs(i, j, m, n, picture));
                room+=1;
            }
        }
    }

    return {room, value};
}