[C++] SWEA 1258번: 행렬찾기

🔗 문제

SW Expert Academy

SW Expert Academy

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

 

🖍 풀이

전체 행렬 크기(N)는 최대 100

 

고맙게도 최소 행렬 개수 문제도 아니며 서브 행렬들은 붙어있지도 않다. 사각형으로 존재한다.

→ 물질이 들어있는 위치를 찾으면 어떤 사각형으로 잘라야 최소 용기 개수인지 고민할 필요 없다.

→ 그 위치에서 서브 행렬 크기만 찾아내면 됨

 

1. 이중포문으로 0이 아닌 위치를 찾는다.
2. 그 위치에서 최대 사각형 크기를 구한다.
3. R x C 와 크기를 저장한다.
4. 찾은 사각형을 0으로 변경한다.

 

출력의 조건을 맞추기 위해 연산자 오버라이딩을 사용해주었다.

bool operator<(const info& a) const
{
    if(order == a.order)
        return r < a.r; // 크기가 같다면 행이 작은 순서대로
    
    return order < a.order; // 크기가 작은 순서대로
}

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 행렬에서 추출된 부분 행렬들을 개수와 그 뒤를 이어 행렬들의 행과 열의 크기를 출력한다.

크기는 행과 열을 곱한 값으로, 크기가 작은 순서대로 출력한다.

예를 들어 3x4 행렬의 크기는 3*4 = 12 이다.

크기가 같을 경우 행이 작은 순으로 출력한다.

 

💾  소스

#include <iostream>
#include <algorithm>
#include <vector>

int N, cnt;
int map[105][105];

struct info
{
public:
    
    info() = default;
    info(const int r, const int c)
    :r(r), c(c), order(r*c) {}
    
    void setter(const int _r, const int _c)
    {
        this->r = _r;
        this->c = _c;
        this->order = r*c;
    }
    
    bool operator<(const info& a) const
    {
        if(order == a.order)
            return r < a.r;
        
        return order < a.order;
    }
    
    int r, c;
    int order;
};

std::vector<info> answer(25);

int findRow(const int x, const int y)
{
    int row = x;
    for(; row<N; ++row)
        if(map[row][y] == 0)
            break;
    
    return row;
}

int findCol(const int x, const int y)
{
    int col = y;
    
    for(; col<N; ++col)
        if(map[x][col] == 0)
            break;
    
    return col;
}

void solve(const int x, const int y)
{
    int row = findRow(x, y);
    int col = findCol(x, y);

    answer[cnt++].setter(row-x, col-y);
    
    // erase
    for(int i=x; i<row; ++i)
        for(int j=y; j<col; ++j)
            map[i][j] = 0;

}

int main()
{
    int T = 0;
    std::cin >> T;
    for(int tc=1; tc<=T; ++tc)
    {

        cnt = 0;
        std::cin >> N;
        for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
                std::cin >> map[i][j];
        
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                if(map[i][j] != 0)
                    solve(i, j);
            }
        }
        
        std::sort(answer.begin(), answer.begin()+ cnt);
        std::cout << '#' << tc << ' ' << cnt<< ' ';
        for(int i=0; i<cnt; ++i)
            std::cout << answer[i].r << ' ' << answer[i].c << ' ';
        std::cout << '\\n';
        
        
    }
    return 0;
}