[Codeforces 1136C] Nastya Is Transposing Matrices

[Codeforces 1136C] Nastya Is Transposing Matrices

문제 설명 : 

( n x m ) 크기의 행렬 A, B가 주어진다. 여기서 A행렬 안에 속하는 부행렬(sub-matrix)를 임의로 선택하여 Transpose 연산을 수행할 수 있다. 여기서 부행렬의 크기는 반드시 정사각행렬이어야 한다. Transpose 연산을 무제한으로 많이 수행할 수 있다고 할 때 A행렬이 B연산으로 바꾸는 것이 가능한지를 묻는 문제이다.

풀이 :

일단 행렬의 Transpose 연산의 특성상 대각선 성분에는 변화가 없고, 그 외에 성분들만 서로 위치를 바꾸게 된다. sub matrix의 크기를 마음대로 설정할 수 있으므로, '행'+'열'을 만족하는 대각성 성분들끼리는 자리를 바꾸는 모든 경우의 수가 가능하다. 그래서 결국 A행렬과 B행렬에서 '행'+'열'의 값이 같은 성분들끼리 비교해서 완전히 일치하면 변환이 가능한 것이고, 하나라도 불일치하는게 있다면 변환이 불가능한 것이다. 

 

주의할 점 : 

1. 위 풀이에서 언급한 행렬에서의 대각선 순회를 하는 구현이 조금 까다롭다. 그런데 조금만 생각을 바꾸면 복잡한 구현을 할 필요가 없다. 그 방법은 바로 입력을 받을 때부터 '행 성분'과 '열 성분'의 좌표 값을 더해서 받는 것이다. 어차피 나중에 '행'+'열'의 값이 같은 것들끼리 모아서 비교할 것이라면 처음부터 입력을 더해서 받자는 의도이다. 이렇게 하면 코드가 훨씬 깔끔해진다.

2. 만약 1번과 같은 발상을 떠올리지 못했다면 그냥 행렬 대각선 순회를 해야한다. 코드 2의 63~70번째 줄에 그에 대한 구현이 나와있다.

배운 점 : 

행렬 대각선 순회 구현 방법, 그리고 굳이 행렬의 형태가 보존되야할 필요가 없다면 입력을 받을 때부터 행+열을 계산해서 받으면 훨씬 간단해진다.

코드 : 

1.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 509
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
// map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
 
 
vector<int> va[SIZE*2],vb[SIZE*2];
int A[SIZE][SIZE],B[SIZE][SIZE];
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m; j++){
            scanf("%d",&A[i][j]);
            va[i+j].push_back(A[i][j]);
        }
    }
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            scanf("%d",&B[i][j]);
            vb[i+j].push_back(B[i][j]);
        }
    }    
 
    for(int i=2 ; i<=n+m ; i++){
        sort(va[i].begin(),va[i].end());
        sort(vb[i].begin(),vb[i].end());
        for(int j=0 ; j<va[i].size() ; j++){
            if(va[i][j]!=vb[i][j]){
                printf("NO\n");
                return 0;
            }
        }
    }
    printf("YES\n");
    return 0;
}
 

2.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 509
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
// map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
int A[SIZE][SIZE],B[SIZE][SIZE];
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m; j++){
            scanf("%d",&A[i][j]);
        }
    }
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            scanf("%d",&B[i][j]);
        }
    }   
 
    for(int i=1 ; i<n+m ; i++){
        int r=1,c=i;
        vector<int> va,vb;
 
        while(r<=n && c>=1){
            if(r<=n && c<=m){
                va.push_back(A[r][c]);
                vb.push_back(B[r][c]);
            }
            r++;
            c--;
        }
        sort(va.begin(),va.end());
        sort(vb.begin(),vb.end());
 
        for(int j=0 ; j<va.size() ; j++){
            if(va[j]!=vb[j]){
                printf("NO\n");
                return 0;
            }
        }
    }
 
    printf("YES\n");
    return 0;
}