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

문제  : Level2 카카오 프렌즈 컬러링북

[ 문제출처 ]  https://programmers.co.kr/learn/courses/30/lessons/1829

 

 

[ 문제풀이 ]

 

이 문제는 주어진 배열에서 영역의 개수를 구하고 가장 큰 영역의 칸의 개수를 구하는 문제이다

 

이 문제는 BFS 를 이용하여 쉽게 해결 하였다.

 

 배열의 원소를 순회 하면서 0이 아닌 칸과 방문하지 않은 칸을 만나게 되면 BFS 함수를 호출 한다.

    -  (BFS 의 반환값으로 해당 영역의 칸의 개수가 반환된다) 이 때 가장 큰 영역의 칸의 개수를 갱신 해준다.

 

 

[ 소스코드 ]

#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
const int MAX = 101;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
bool check[MAX][MAX];
int bfs(int x, int y, vector<vector<int>>& map) {
    int area = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (0 > nx || nx >= map.size() || 0 > ny || ny >= map[0].size()) continue;
            if (check[nx][ny] || map[x][y] != map[nx][ny]) continue;
            q.push(make_pair(nx, ny)), area++, check[nx][ny] = true;
        }
    }
    return area;
}
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    vector<int> answer(2);
    memset(check, false, sizeof(check));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (picture[i][j] == 0 || check[i][j]) continue;
            number_of_area++;
            int now = bfs(i, j, picture);
            max_size_of_one_area = max(max_size_of_one_area, now);
        }
    }
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}