[Programmers] Lv2. 카카오프렌즈 컬러링북 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

BFS로 풀 수 있는 쉬운 문제입니다.

1. 색칠되지 않은 영역은 지나간다.
2. 색칠되어 있고, 방문한 적이 없는 픽셀이라면, 해당 픽셀을 기준으로 상하좌우 BFS 탐색을 시작한다.
3. BFS 탐색이 끝났다면 영역 개수를 1개 늘려주고, 이전 영역 크기와 비교하여 더 큰 값으로 갱신한다.

 

✏️소스 코드 및 결과

#include <vector>
#include <queue>
using namespace std;
const int DIRECTION_COUNT = 4;
const int rowDirections[DIRECTION_COUNT] = { -1, 1, 0, 0 };
const int colDirections[DIRECTION_COUNT] = { 0, 0, -1, 1 };

struct Pixel {
    Pixel() { }
    Pixel(int color, int row, int col) : _color(color), _row(row), _col(col) { }

    int     _color;
    int     _row;
    int     _col;
};

int FindArea(vector<vector<Pixel>>& board, vector<vector<bool>>& visited, int m, int n, Pixel selection) {
    int area = 1;
    visited[selection._row][selection._col] = true;
    
    queue<Pixel> coloredAreas;
    coloredAreas.emplace(selection);

    while (!coloredAreas.empty()) {
        Pixel pixel = coloredAreas.front();
        coloredAreas.pop();

        for (int i = 0; i < DIRECTION_COUNT; i++) {
            int nextRow = pixel._row + rowDirections[i];
            int nextCol = pixel._col + colDirections[i];

            if (nextRow < 0 or nextRow >= m or nextCol < 0 or nextCol >= n)
                continue;
            if (board[nextRow][nextCol]._color != pixel._color or board[nextRow][nextCol]._color == 0 or visited[nextRow][nextCol])
                continue;

            coloredAreas.emplace(Pixel(pixel._color, nextRow, nextCol));
            visited[nextRow][nextCol] = true;
            area++;
        }
    }

    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<vector<Pixel>> board(m, vector<Pixel>(n));
    vector<vector<bool>> visited(m, vector<bool>(n, false));

    for (int row = 0; row < m; row++)
        for (int col = 0; col < n; col++)
            board[row][col] = Pixel(picture[row][col], row, col);

    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            if (visited[row][col] or board[row][col]._color == 0)
                continue;

            number_of_area++;
            max_size_of_one_area = max(max_size_of_one_area, FindArea(board, visited, m, n, board[row][col]));
        }
    }

    return { number_of_area, max_size_of_one_area };
}

 

채점 케이스가 1개 밖에 없네요?