[BOJ/백준][Gold4] 17140 : 이차원 배열과 연산 (C++)

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

 

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

 

[풀이]

R 연산에 대한 함수만 정의하고 배열을 반시계 방향으로 회전하는 함수를 들어서 이용하면 C 연산은 따로 정의하지 않아도 해결할 수 있다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using vvi = vector<vector<int>>;
int r,c,k;

vvi rot(vvi& m){
    int csz = m.size();
    int rsz = m[0].size();
    vector<vector<int>> ret(rsz,vector<int>(csz));
    for(int i=0;i<rsz;i++)
        for(int j=0;j<csz;j++) ret[i][j] = m[j][rsz-i-1];

    return ret;
}

vvi R(vvi& m){
    vvi tmp;
    int mxl = 0;
    for(auto v : m){
        map<int,int> cntMap;
        for(auto i : v) {
            if(i!=0) cntMap[i]++;
        }

        vector<pair<int,int>> ov;
        for(auto p : cntMap){
            ov.push_back({p.second,p.first});
        }
        sort(ov.begin(),ov.end());
        vector<int> res;
        for(auto o : ov){
            res.push_back(o.second);
            res.push_back(o.first);
        }
        mxl = max(mxl,(int)res.size());
        tmp.push_back(res);
    }
    mxl = min(100,mxl);
    for(auto& t : tmp) t.resize(mxl);
    return tmp;
}

int main(){
    scanf("%d%d%d",&r,&c,&k);
    r--,c--;
    vvi map;
    for(int i=0;i<3;i++){
        vector<int> a(3);
        for(int j=0;j<3;j++) scanf("%d",&a[j]);
        map.push_back(a);
    }
    int time = 0;
    while(1){
        int rsz = map.size();
        int csz = map[0].size();
        if(r < rsz && c < csz && map[r][c]==k) break;
        if(time==100){
            time = -1;
            break;
        }
        if(rsz >= csz){
            map = R(map);
        }else{
            map = rot(map);
            map = R(map);
            for(int i=0;i<3;i++) map=rot(map);
        }
        time++;
    }
    printf("%d",time);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17140.cpp