1258 행렬찾기

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
#define NS 102
int map[NS][NS];
int chk[NS][NS];
int N;
int ret;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
	int size, y, x;
};
bool cmp(Data a, Data b) {
	if (a.size == b.size)return a.y < b.y;
	else return a.size < b.size;
}
vector<Data>v;

struct Matrix {
	Matrix() {
		int T;
		scanf("%d", &T);
		for (int t = 1; t <= T; t++) {
			init();
			scanf("%d", &N);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					scanf("%d", &map[i][j]);
				}
			}
			research();

			printf("#%d %d ", t, ret);
			sort(v.begin(), v.end(), cmp);//배열 크기가 작고 같은경우에는 y가 작은순으로 정렬
			for (int i = 0; i < v.size(); i++) {
				printf("%d %d ", v[i].y, v[i].x);
			}
			printf("\n");
		}
	}
	void yxChk(int idx,int y,int x) {
		int y1 = 0;
		int x1 = 0;
		for (int i = y; i <= N; i++) {//y체크
			y1++;
			if (map[i][x] == 0||i==N) {
				y1--;
				v[idx].y = y1;
				break;
			}
		}
		for (int j = x; j <= N; j++) {
			x1++;
			if (map[y][j] == 0||j==N) {
				x1--;
				v[idx].x = x1;
				break;
			}
		}
		v[idx].size = v[idx].y*v[idx].x;
		return;
	}

	void research() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0 && chk[i][j] == 0) {
					v.push_back({ 0,i,j });
					ret++;
					chk[i][j] = ret;
					dfs(i, j, ret);
				}
			}
		}
		for (int i = 0; i < v.size(); i++) {
			yxChk(i,v[i].y,v[i].x);
		}
	}
	void init() {
		ret = 0;
		v.clear();//배열 초기화
		memset(chk, 0, sizeof(chk));
	}
	bool safe(int y, int x) {
		return 0 <= y && y < N && 0 <= x && x < N;
	}
	void dfs(int y, int x, int cnt) {
		for (int dir = 0; dir < 4; dir++) {
			Data n;
			n.y = y + dy[dir]; n.x = x + dx[dir];
			if (safe(n.y, n.x) && map[n.y][n.x] != 0 && chk[n.y][n.x] == 0) {
				chk[n.y][n.x] = cnt;
				dfs(n.y, n.x, cnt);
			}
		}
	}
}Matrix;
int main(void) {
	return 0;
}

행렬 찾기 문제는 포인트를 집어드리자면 제가 생각했을대 각 행렬을 구분 할줄 알아야하고 

구분된거에대해서 y값과 x값을 뽑아낼 수있어야합니다 그렇게 되면 그냥 일사천리로 값이 나오게 됩니다.

사실 말로 하면 누가 못해 하지만 차근 차근 생각해보면서 하셔야합니다. 두가지 이상의 방식있지만 

저는 0,0 이 1의 구역의 시작이면 0,1  0,2 0,N 까지 돌면서 0이 나오면 그위치전의 갯수를 x라 지칭하고

1.0 2.0 3,0 N,0 을 반복하면 0이나오는 위치의 갯수를 y로해서 했는데

 

그냥 dfs를 돌면서 섬의 번호를 지정할때 그섬의 y와 x의 최대값을 찾고

시작점의y ,x를 빼면됩니다. 그렇게 하면 더 쉽게 구현이 가능해지겠죠?

 

예를 들자면  1 1 1 0 0 0
                  1 1 1 0 0 0

                  0 0 0 0 2 2 의 배열로 나누면서 하는것인데 

1의 경우 0,0으로 시작해서 dfs를 돌면서 나오는 y,x의 최대값이 1,2 인데 

그값에서 시작점 0,0을 빼면 즉 y의 길이는 1-0 +1 

                                        x의 길이느 2-0 +1 으로 2 * 3의  크기를 가짐을 계산을 통해 알 수 있습니다.

 

수식으로 굳이 나타내자면 

y의 길이는 Max Y - Start Y +1;

x의 길이는 Max X - start X +1 ; 로 나타낼 수있습니다. 알고리즘에서 가장 중요한것은 수식으로 표현 할 줄 알아야하는것입니다. 여러분들도 파이팅!@!@!