이차원 배열과 연산

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1137 ~ 12:20
int r,c,k,ans;
int R=3,C=3;
int board[105][105];
int tmp[105][105];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c >> k;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cin >> board[i][j];

    while(true)
    {
        if(board[r-1][c-1] == k)
            goto stop;
        else if(ans >= 100)
        {
            ans = -1;
            goto stop;
        }
        ans++;
        /* R 연산 */
        if(R >= C){
            int maxC=C;
            for(int i=0;i<R;i++)
            {
                vector<pair<int,int>> v;
                map<int,int> m;
                for(int a=0;a<C;a++)
                {
                    if(board[i][a] == 0) continue;
                    m[board[i][a]]++;
                }
                for(auto it=m.begin();it != m.end();it++)
                    v.push_back({it->second, it->first}); // {등장 횟수, 숫자}
                sort(v.begin(), v.end()); // 등장횟수 오름차순, 같다면 숫자 오름차순
                int idx=0;
                for(int a=0;a<v.size();a++)
                {
                    int num =v[a].second;
                    int cnt = v[a].first;
                    tmp[i][idx++] = num;
                    tmp[i][idx++] = cnt;
                }
                maxC = max(maxC, idx);
            }
            C = maxC;
            if(C > 100) C = 100;
        }else{
            /* C 연산 */
            int maxR=R;
            for(int i=0;i<C;i++)
            {
                vector<pair<int,int>> v;
                map<int,int> m;
                for(int a=0;a<R;a++)
                {
                    if(board[a][i] == 0) continue;
                    m[board[a][i]]++;
                }
                for(auto it=m.begin();it != m.end();it++)
                    v.push_back({it->second, it->first}); // {등장 횟수, 숫자}
                sort(v.begin(), v.end()); // 등장횟수 오름차순, 같다면 숫자 오름차순
                int idx=0;
                for(int a=0;a<v.size();a++)
                {
                    int num =v[a].second;
                    int cnt = v[a].first;
                    tmp[idx++][i] = num;
                    tmp[idx++][i] = cnt;
                }
                maxR = max(maxR, idx);
            }
            R = maxR;
            if(R > 100) R = 100;
        }
        for(int i=0;i<R;i++)
            for(int j=0;j<C;j++)
            {
                board[i][j] = tmp[i][j];
                tmp[i][j] = 0;
            }
    }
    stop:;
    cout << ans;
    return 0;
}

• 핵심
  : map을 활용해서 count한 뒤 pair<등장횟수,숫자> 로 vector에 넣은 뒤 정렬하는 것

• 주의
  : 시간복잡도 계산을 해보니 최대 O(N^3) = 10^6승 연산 정도라서 충분히 가능!