[1258번] 행렬찾기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

2. BFS

BFS를 통해 각 면적의 가로,세로를 구해주고 크기는 가로*세로로 구한다.

그리고 정렬에서 compare 함수를 이용하여 크기가 작은 순, 크기가 같다면 행이 작은 순으로 만든다.

소스 코드 : 

#include <iostream>
using namespace std;
#define max(a,b)(a > b ? a : b)
 
 
int arr[102][102];
bool visit[102][102];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
 
struct INFO {
    int y, x, sz;
    int height, width;
};
struct TUPLE {
    int y, x, sz;
};
TUPLE ans[102];
TUPLE tmp[102];
int idx;
 
INFO q[1000002];
int first, last;
void init() {
    for (int i = 0; i < 102; i++)
        for (int j = 0; j < 102; j++)
            visit[i][j] = false;
    first = last = 0;
    idx = 0;
}
 
bool comp(int p, int q) {
    if (ans[p].sz == ans[q].sz)
        return ans[p].y < ans[q].y;
    return ans[p].sz < ans[q].sz;
}
void mergeSort(int s, int e) {
    if (s >= e)
        return;
 
    int m = (s + e) / 2;
 
    mergeSort(s, m);
    mergeSort(m + 1, e);
 
    int s1 = s, s2 = m + 1;
    int idx = s;
 
    while (s1 <= m || s2 <= e) {
        if (s2 > e || (s1 <= m && comp(s1, s2)))
            tmp[idx++] = ans[s1++];
        else
            tmp[idx++] = ans[s2++];
    }
    for (int i = s; i <= e; i++)
        ans[i] = tmp[i];    
}
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        init();
 
        int n;
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &arr[i][j]);
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!arr[i][j] || visit[i][j])
                    continue;
 
                q[last++] = { i,j,1,1,1 };
                int maxHeight = -1, maxWidth = -1;
                while (first < last) {
                    INFO here = q[first++];
                    if (visit[here.y][here.x])
                        continue;
 
                    visit[here.y][here.x] = true;
 
                    for (int i = 0; i < 4; i++) {
                        int ny = here.y + dy[i];
                        int nx = here.x + dx[i];
                        if (0 <= ny && ny < n && 0 <= nx && nx < n && arr[ny][nx]) {
 
                            maxHeight = max(here.height + dy[i], maxHeight);
                            maxWidth = max(here.width + dx[i], maxWidth);
                            q[last++] = { ny,nx,here.sz + 1, here.height + dy[i], here.width + dx[i] };
                        }
                    }
                }
 
                ans[idx++] = { maxHeight, maxWidth, maxHeight * maxWidth };
            }
        }
 
 
        mergeSort(0, idx - 1);
 
        printf("#%d %d ", tc, idx);
        for (int i = 0; i < idx; i++)
            printf("%d %d ", ans[i].y, ans[i].x);
        printf("\n");
    }
 
 
    return 0;
}