7일차 - 행렬찾기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;
#define number 100
int dirX[4] = { 1,0,-1,0 };//동남서북
int dirY[4] = { 0,-1,0,1 };//동남서북
 
int arr[number][number] = { 0, };//체크 어레이는 필요하지 않는다. 
int chk[number][number] = { 0, };
int N;


typedef struct
{
	int row;
	int col;
	int width;
}Data_struct;

vector<Data_struct> vTemp;

bool cmp(Data_struct a, Data_struct b)
{
	if (a.width == b.width)
	{
		return a.row < b.row;
	}
	else
	{
		return a.width < b.width;
	}
}

void input()
{
	cin >> N;

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

void initialize()
{
	vTemp.clear();
	for (int i = 0; i < number; i++)
	{
		for (int j = 0; j < number; j++)
		{
			arr[i][j] = 0;
			chk[i][j] = 0;
		}
	}
}

void Find_Size(int y, int x)
{
	int Tx = x;
	int Ty = y;
	int Garo, Sero;
	Garo = Sero = 0;
	while (arr[Ty][x] != 0) 
	{
		Sero++; Ty++; 
	}

	while (arr[y][Tx] != 0) 
	{
		Garo++; Tx++; 
	}

	Data_struct stTemp;
	stTemp.row = Sero;
	stTemp.col = Garo;
	stTemp.width = Garo*Sero;

	vTemp.push_back(stTemp);
}





void bfs(int y, int x)
{
	chk[y][x] = 1;
	queue<pair<int, int>> qTemp;
	qTemp.push(make_pair(y, x));
	while (!qTemp.empty())
	{
		int ytmp = qTemp.front().first;
		int xtmp = qTemp.front().second;
		qTemp.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = ytmp + dirY[i];
			int nx = xtmp + dirX[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < N)
			{
				if (arr[ny][nx] != 0 && chk[ny][nx] == 0)
				{
					chk[ny][nx] = 1;
					qTemp.push(make_pair(ny, nx));
				}
			}			
		}
	}
}

int main(void)
{
	int iTestcase;
	cin >> iTestcase;

	for (int m = 0; m < iTestcase; m++)
	{
		initialize();
		input();

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] != 0 && chk[i][j] == 0)
				{
					bfs(i, j);
					Find_Size(i, j);
				}
			}
		}


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

		cout << "#" << m + 1 << " " << vTemp.size() << " ";

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

		cout << endl;
	}
	return 0;
}

이문제 풀때,
1.

for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] != 0 && chk[i][j] == 0)
				{
					bfs(i, j);
					Find_Size(i, j);
				}
			}
		}

이런식으로 이중포문 bfs와 내부함수 또만드는 구조

2. bfs에서

if (ny >= 0 && ny < N && nx >= 0 && nx < N)
			{
				if (arr[ny][nx] != 0 && chk[ny][nx] == 0)
				{
					chk[ny][nx] = 1;
					qTemp.push(make_pair(ny, nx));
				}
			}	

        이조건 제대로 안만들면 무한루프 빠지게된다.

3. 이 문제에서 확실하게 설명이 없었는데,
   난 이문제 못풀었다.
   근데 사실상 직사각형 매핑 && 직사각형 주변에 다 0(단순 bfs로 접근하면 안됨-이문제는 맞는예시)
   이부분에 디테일한 조건이 부족한거로보임.