카카오프렌즈 컬러링북(Lv2)

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;


bool cmp(int a, int b)
{
    return a > b;
}

int dirX[] = { -1,0,1,0 };//x축 좌표들
int dirY[] = { 0,-1,0,1 };//y축 좌표들 

bool vvVisited[101][101];

//m:전체 x사이즈 row
//n:전체 y사이즈 column
//a:picture 좌표 x
//b:picture 좌표 y
int BFS(int m, int n, int x, int y, vector<vector<int>> picture)
{
    int iCurrentNum = picture[x][y];//인접 행렬들이 이 숫자들과 같아야한다.
    int answer = 1;
    int nx; int ny;
    queue<pair<int, int>> qCon;
    qCon.push(make_pair(x, y));
    vvVisited[x][y] = true;

    while (!qCon.empty())
    {
        int x = qCon.front().first;
        int y = qCon.front().second;
        qCon.pop();
        for (int i = 0; i < 4; i++)
        {
            nx = x + dirX[i];
            ny = y + dirY[i];
            // 하기의 조건문은.
            //방문하지 않은 상태이며
            //인접한 부분들과 색이 일치하는 경우입니다.
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && vvVisited[nx][ny] == false && iCurrentNum == picture[nx][ny])
            {
                vvVisited[nx][ny] = true;
                qCon.push(make_pair(nx, ny));
                answer++;//인접한 부분들과 색이 일치하는 경우 return value ++;해준다. 
            }
        }
    }
    return answer;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
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> vmaxSize;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            vvVisited[i][j] = false;
        }
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {//숫자가 0이 아니어야함.
            if ((picture[i][j] != 0) && (vvVisited[i][j] == false))//방문 안해야 하고, 숫자가
            {//vvVisited는 위에서 BFS 에서 방문처리 하게된다. 
                int iTemp = BFS(m, n, i, j, picture);
                vmaxSize.push_back(iTemp);
                number_of_area++;// BFS 를 통해 인접 행렬들의 몇개의 영역이 있는지 알아내게 된다.
                //BFS를 통해 인접 행렬들이 아닌 경우에는 
            }
        }
    }

    sort(vmaxSize.begin(), vmaxSize.end(), cmp);


    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = vmaxSize[0];
    return answer;
}

int main()
{
    vector<vector<int>> vTemp = { {1, 1, 1, 0},{1, 2, 2, 0},{1, 0, 0, 1},{0, 0, 0, 1},{0, 0, 0, 3},{0, 0, 0, 3} };
    int x = 6;
    int y = 4;

    vector<int> vResult;

    vResult = solution(x, y, vTemp);

  
}

질좋은 문제. 설명은 주석으로
BFS할 때 이런 queue.push 이후,
하나씩 팝하면서
x,y 좌표계 이동하고
bool btmp 2차원에 true 주며 방문기록 체크하는 방식 중요하다.

queue에서 처음꺼 팝하고,
팝한부분에서 BFS 로 주변살피고,
트정조건(문제에서 나옴 - x,y범위를 넘치지 않아야하며, 문제에서 주는 조건들 만족한다)
방문기록 하고,
BFS를 다시 하기 위해 다시 push 한다.
전체 while문은 (!queue.empty())
으로 이런 스타일의 BFS 알아놔야함