[CF 1684C]Column Swapping

[CF 1684C]Column Swapping - 1400

문제 설명

n개의 행과 m개의 열이 있으며 모든 값이 양의 정수인 격자가 주어진다. 이때 임의의 2개의 열의 위치(동일 위치끼리도 가능)를 서로 바꾸어 모든 행이 오름차순으로 정렬된 상태에 놓이게 만들 수 있는가? 만약 그렇다면 위치를 서로 교환할 2개의 열의 인덱스를 출력하고 그렇지 않으면 -1을 출력하라.

문제 풀이

1. 문제를 단순화시켜서, 열이 1개짜리인 1xm 짜리 행렬(수열)이라고 가정해보자. 이 수열이 정확히 1번의 swap연산을 통해서 $a_i <= a_{i+1}$을 만족할 수 있는지 확인하는 방법을 찾은 후에 nxm 행렬로 확장하는 생각을 해보자.
2. 열이 1개짜리인 수열에서 확인하는 방법은, a수열을 오름차순 정렬한 수열을 sorted배열이라고 했을 때 sorted[i]와 a[i]의 값이 다른 개수가 0개 또는 2개여야만 한다. 2개 이상이면 1번의 swap으로 고칠 수 없다는 뜻이다. 값이 다른 지점의 인덱스끼리 swap하고나면 반드시 오름차순 정렬을 만족할 것이다.
   1. 그럼 이제 이 방법을 n개의 열에 대해서 적용해보자. 이 문제에서는 어떤 column을 swap하면 해당 column에 매달려있는(마치 꼬치처럼)나머지 원소들도 줄줄이 swap될 것이다. 따라서 모든 열에서 (2번에서 설명했던) 값이 다른 지점의 인덱스는 모두 같아야만 한다.
3. 다시말해, 나는 모든 row에서 sorted[i]와 a[i]의 값이 다른 지점의 인덱스가 모두 일관되는지만 확인해보면 된다.

소스 코드

int main(){
  int t;  scanf("%d",&t);
  while(t--){
    int n,m;  scanf("%d %d",&n,&m);
    vector<vector<int>> a(n,vector<int>(m));
    for(int i=0 ; i<n ; i++)
      for(int j=0 ; j<m ; j++)
        scanf("%d",&a[i][j]);

    vector<int> swapped;

    for(int i=0 ; i<n ; i++){
      vector<int> sorted = a[i];
      sort(sorted.begin(),sorted.end());
      for(int j=0 ; j<m ; j++){
        if(a[i][j] != sorted[j]){
          swapped.push_back(j);
        }
      }
      if(swapped.size() > 0) break;
    }

    int imp = 0;
    if(swapped.size() == 0){
      imp = -1;
    } else if(swapped.size() > 2){
      imp = 1;
    } else {
      for(int i=0 ; i<n ; i++){
        swap(a[i][swapped[0]],a[i][swapped[1]]);
        for(int j=0 ; j<m-1 ; j++){
          if(a[i][j] > a[i][j+1]){
            imp = 1;
            break;
          }
        }
      }
    }

    if(imp == 1){
      printf("-1\n");
    } else if(imp == -1){
      printf("1 1\n");
    } else{
      printf("%d %d\n",swapped[0]+1,swapped[1]+1);
    } 
  }
}