[NHN] 모의 테스트 - C++ 행렬의 영역

DFS를 이용한 문제이다.

 

---

1. Solution 코드

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 10;
const int DIR = 4;
const int dx[DIR] = {-1, 1, 0, 0};
const int dy[DIR] = {0, 0, -1, 1};

bool visit[MAX_N][MAX_N];


int BFS(int x, int y, int sizeOfMatrix, int **matrix){
	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;
	
	
	while(!q.empty()){
		int curX = q.front().first;		// x
		int curY = q.front().second;	// y
		
		q.pop();
		
		for(int i = 0; i < DIR; i++){
			int nextX = curX + dx[i];
			int nextY = curY + dy[i];
			
			if(nextX >= 0 && nextX < sizeOfMatrix && nextY < sizeOfMatrix && nextY >= 0){
				if(matrix[nextX][nextY] && !visit[nextX][nextY]){
					++count;
					q.push(make_pair(nextX, nextY));
					visit[nextX][nextY] = true;
				}
			}
		}
		
	}
	
	return count;
}


void solution(int sizeOfMatrix, int **matrix) {
  // TODO: 이곳에 코드를 작성하세요.
	priority_queue< int, vector<int>, greater<int> > q;
	
	for(int i = 0; i < sizeOfMatrix; i++){
		for(int j = 0; j < sizeOfMatrix; j++){
			visit[i][j] = false;
		}
	}
	
	
	for(int i = 0; i < sizeOfMatrix; i++){
		for(int j = 0; j < sizeOfMatrix; j++){
			int size = BFS(i, j, sizeOfMatrix, matrix);
			if(size > 0)
				q.push(size);
		}
	}
	
	printf("%d\n", q.size());
	
	while(!q.empty()){
		printf("%d ", q.top());
		q.pop();
	}
}

struct input_data {
  int sizeOfMatrix;
  int **matrix;
};

void process_stdin(struct input_data& inputData) {
  string line;
  istringstream iss;

  getline(cin, line);
  iss.str(line);
  iss >> inputData.sizeOfMatrix;

  inputData.matrix = new int*[inputData.sizeOfMatrix];
  for (int i = 0; i < inputData.sizeOfMatrix; i++) {
    getline(cin, line);
    iss.clear();
    iss.str(line);
    inputData.matrix[i] = new int[inputData.sizeOfMatrix];
    for (int j = 0; j < inputData.sizeOfMatrix; j++) {
      iss >> inputData.matrix[i][j];
    }
  }
}

int main() {
  struct input_data inputData;
  process_stdin(inputData);

  solution(inputData.sizeOfMatrix, inputData.matrix);
  return 0;
}