NHN 2020 pre-test 1차 모의고사 - 행렬의 영역(c++)

풀이

#include <iostream>
#include <sstream>
#include <queue>
using namespace std;

int BFS(int x, int y, int sizeOfMatrix, int **matrix, bool **visit){
    if(!matrix[x][y] || visit[x][y]) return -1;
	
    int count = 1;
    queue< pair<int,int> > q;
    q.push( make_pair(x, y) );
    visit[x][y] = true;
    int dx[] = {1,-1,0,0};
    int dy[] = {0,0,1,-1};

    while(!q.empty()){
        int sx = q.front().first;
        int sy = q.front().second;
		
        q.pop();
		
        for(int i=0; i<4; i++){
            int nx = sx + dx[i];
            int ny = sy + dy[i];
			
            if(nx>=0 && ny>=0 && nx<sizeOfMatrix && ny<sizeOfMatrix){
               if(matrix[nx][ny] && !visit[nx][ny]){
                    ++count;
                    q.push( make_pair(nx, ny) );
                    visit[nx][ny] = true;
                }
            }
        }
    }
	
    return count;
}

void solution(int sizeOfMatrix, int **matrix) {
    priority_queue< int, vector<int>, greater<int> > q;
    bool **visit = new bool*[sizeOfMatrix];
	
    for(int i=0; i<sizeOfMatrix; i++){
        visit[i] = new bool[sizeOfMatrix]();
    }
	
    for(int i=0; i<sizeOfMatrix; i++){
        for(int j=0; j<sizeOfMatrix; j++){
            int size = BFS(i, j, sizeOfMatrix, matrix, visit);
            if(size>0) q.push(size);
        }
    }
	
    cout << q.size() << "\n";
	
    while(!q.empty()){
        cout << q.top() << " ";
        q.pop();
    }
}