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

전~형적인 BFS 문제.

BFS를 대표하는 문제라고도 할 수 있겠다.

 

아래 그림은 두 개의 영역으로 구성돼 있고, 각각의 크기는 6,4 이다.

이것을 그러면 코드로 어떻게 판단할 것이냐?

브루트포스로 처음부터 끝까지 돌면서, 

0보다 큰 수를 만났을 때 BFS를 돌리는 것이다.

그러면 상하좌우에 있는 같은 색깔을 모두 count하게 되고, 

모든 주변의 색깔을 count했다면 해당 count가 max인 값이 answer의 두 번째 인자가 된다.

이 때 이미 검사한 타일은 따로 저장해두면서 지나가야 한다.

(BFS를 잘 설명해놓은 곳 -> https://blog.encrypted.gg/941?category=773649) 

    1110
    1110
    0001
    0001
    0001
    0001

#include <bits/stdc++.h>

using namespace std;

int board[101][101];
int dist[101][101];
queue<pair<int, int>> Q;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sizeOfColor;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    for (int i = 0; i < 101; i++)
        fill(dist[i], dist[i] + 101, 0);
    
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = picture[i][j];
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (board[i][j] == 0 || dist[i][j] >= 1)
                continue;
                
            // BFS 시작.
            Q.push({i, j});
            number_of_area++;
            int color = board[i][j];
            dist[i][j] = 1;
            sizeOfColor = 1;
            while (!Q.empty())
            {            
                auto t = Q.front();
                Q.pop();
                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = t.first + dx[dir];
                    int ny = t.second + dy[dir];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                        continue;
                    if (board[nx][ny] != color || dist[nx][ny] >= 1)
                        continue;
                    dist[nx][ny] = 1;
                    Q.push({nx, ny});
                    sizeOfColor++;
                }
            }
            max_size_of_one_area = max(max_size_of_one_area, sizeOfColor);
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;

}