1258. [S/W 문제해결 응용] 7일차 - 행렬찾기

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN&categoryId=AV18LoAqItcCFAZN&categoryType=CODE

SW Expert Academy

 

 

visit처리해주면서 영역 구분하면 되는 문제. 간단히 해결.

///////

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

int arr[100][100];
bool visit[100][100];


int N;


struct Node {

	int row;
	int col;
	int cost;

	bool operator<(const Node& e)
		const {

		if (cost != e.cost)
		{
			return cost < e.cost;
		}

		return row < e.row;
	}
};

vector<Node> vec;


void findArea(int y, int x)
{
	int row = 1;
	for (int i = y + 1; i < N; i++)
	{
		if (arr[i][x] != 0 && !visit[i][x])
		{
			row++;
		}
		else if (arr[i][x] == 0)
		{
			break;
		}
	}

	int col = 1;

	for (int j = x + 1; j < N; j++)
	{
		if (arr[y][j] != 0 && !visit[y][j])
		{
			col++;

		}
		else if (arr[y][j] == 0)
		{
			break;
		}
	}


	for (int i = y; i < y + row; i++)
	{
		for (int j = x; j < x + col; j++)
		{
			visit[i][j] = true;
		}
	}

	vec.push_back({ row,col,row * col });
}

int main(int argc, char** argv)
{
	int test_case;
	int T;


	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		memset(visit, 0, sizeof(visit));
		vec.clear();

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
			}
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (!visit[i][j] && arr[i][j] != 0)
				{
					visit[i][j] = true;
					findArea(i, j);
				}
			}
		}
		sort(vec.begin(), vec.end());

		cout << "#" << test_case << " " << vec.size() << " ";
		for (int i = 0; i < vec.size(); i++)
		{
			cout << vec[i].row << " " << vec[i].col << " ";
		}
		cout << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}