BOJ 14204 : 표 정렬

• 문제 링크 : boj.kr/14204
• 난이도 : G5
• 태그 : 정렬, 구현

14204번: 표 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int matrix[50][50];
int n, m;

void swap_row(int a, int b) {
    for(int i = 0; i < m; i++) {
        int temp = matrix[a][i];
        matrix[a][i] = matrix[b][i];
        matrix[b][i] = temp;
    }
}
void swap_col(int a, int b) {
    for(int i = 0; i < n; i++) {
        int temp = matrix[i][a];
        matrix[i][a] = matrix[i][b];
        matrix[i][b] = temp;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(matrix[i][0] > matrix[j][0]) {
                swap_row(i,j);
            }
        }
    }
    for(int i = 0; i < m; i++) {
        for(int j = i + 1; j < m; j++) {
            if(matrix[0][i] > matrix[0][j]) {
                swap_col(i,j);
            }
        }
    }

    int before = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(matrix[i][j] < before) {
                cout << 0;
                return 0;
            }
            before = matrix[i][j];
        }
    }
    cout << 1;

    return 0;
}

---

풀이

첫 행과 첫 열을 기준으로 보고 정렬을 해준다.

첫 행과 첫 열이 정렬된 상태에서 이들을 바꾸지 않고 다른 원소를 정렬하는 방법은 없다. 따라서 첫 행과 첫 열이 정렬된 상태에서 전체적으로 정렬이 이루어지지 않았다면 이 표는 정렬될 수 없는 표이다.

 

 

 

N과 M이 충분히 작기 때문에 앞의 풀이로도 풀 수 있다. 정렬을 O(NlogN)으로 한다고 가정했을 때, 앞의 풀이의 시간 복잡도는 O(NMlogNM)이다. 하지만 앞의 풀이에 조금의 관찰을 더하면 O(NM)에도 풀 수 있다.

열 교체에 대해 관찰해보면 두 인접한 행에서 각 인접한 원소들의 차는 전부 같아야 함을 알 수 있다. 마찬가지로 두 인접한 열에서 각 인접한 원소들의 차는 전부 같아야 함을 알 수 있다. 차가 같은지 확인하는 과정은 O(NM)으로도 충분하다.