[C++] nhn 사전 테스트 - 행렬의 영역

사전테스트인데 pre-test로 헷갈렸다. 죄송함니다.ㅠㅠ

사전테스트 행렬의 영역 1번

 

효율성 테스트를 통과하지 못했다 ㅠㅠ. 앞으로의 코딩 밑거름이 되길..

 

 

(입력)

6

0 1 1 0 0 0

0 1 1 0 1 1

0 0 0 0 1 1

0 0 0 0 1 1

1 1 0 0 1 0

1 1 1 0 0 0

 

(출력)

3

4 5 7

입력은 N*N 행렬의 크기, 행렬의 원소를 개행문자로 입력한다.

출력은 영역의 갯수, 영역의 크기를 출력한다. 영역의 크기는 오름차순 정렬되어야 한다.

 

dfs는 깊이 우선 탐색 알고리즘을 응용하여 작성하였지만, 기억나는데로 짠거라 아닐수도 있다...

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

stack<pair<int, int> > s;
vector<vector<bool> > visit;

int dfs(int **matrix, int i, int j)
{
	//(i,j)가 시작점.
	int area = 0;
	s.push(pair<int, int>(i,j));
	while(!s.empty())
	{
		int ci = s.top().first;
		int cj = s.top().second;
		visit[ci][cj] = true;
		if(cj < visit.size() - 1 && matrix[ci][cj+1] == 1 && visit.at(ci)[cj+1] == false) //오른쪽 방향
		{
			s.push(pair<int, int> (ci, cj+1));
		}
		else if(cj > 1 && matrix[ci][cj-1] == 1 && visit.at(ci)[cj-1] == false) //왼쪽 방향
		{
			s.push(pair<int, int> (ci, cj-1));
		} 
		else if(ci > 1 && matrix[ci-1][cj] == 1 && visit.at(ci-1)[cj] == false) //위쪽 방향
		{
			s.push(pair<int, int> (ci, cj-1));
		} 
		else if(ci < visit.size() - 1 && matrix[ci+1][cj] == 1 && visit.at(ci+1)[cj] == false) //아래 방향
		{
			s.push(pair<int, int> (ci+1, cj));
		}
		else
		{
			s.pop();
			area += 1;
		}
	}
	return area;
}
	
	void solution(int sizeOfMatrix, int **matrix) {
  // TODO: 이곳에 코드를 작성하세요.
	vector<bool> vis1 (sizeOfMatrix, false);
	for(int i = 0; i < sizeOfMatrix; i++)
		visit.push_back(vis1);
	

	vector<int> answer;
	for(int i = 0 ; i < sizeOfMatrix; i ++)
	{
		for(int j = 0; j <sizeOfMatrix; j ++)
		{
			if(visit[i][j] == false && (matrix[i][j] == 1))
			{
					answer.push_back(dfs(matrix, i, j));
			}
		}
	}	
	sort(answer.begin(), answer.end());
	cout << answer.size() << endl;
	for(int i = 0; i < answer.size(); i++)
		cout << answer[i] << " "; 


}

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;
}