1. 문제설명

크기 3x3 배열에 값이 채워져있다.
R 연산과 C 연산이 있다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
예를 들어 다음과 같은 입력이 있다고 해보자
```
1 2 3
1 2 1
2 1 3
3 3 3
```

이 입력은 다음 과정을 통해 총 2번 연산하게 된다.

2번 연산하면 (1,2) 자리에 목표값 3이 존재하기 때문이다.

2 1
1 3
3 3
  
// 최근 결과 값이 행의 개수 == 열의 개수, 즉 R 연산
1 1 2
1 2 1 3 1
3
  
// 최근 결과 값이 최대 열의 개수는 6이고, 행은 3이므로 C연산
3 1 1 3 1
1 1 1 1 1
1 2 2
2 1 1
3
1

다른 블로그보면 문제 설명하고 코드만 띡 올려놨는데,
상세한 과정을 공유드리고 싶었다.
문제 분류
- Implementation, Sorting, Simulation

2. 알고리즘 설계

값의 복사와 정렬 조건을 잘 명시해주면 된다.
0은 정렬 과정에 들어가면 안되므로, 임시로 저장할 때는 0을 배제 시켜준다.

재귀로 구현했고, 탈출 조건은 다음과 같다.

  if (A[r][c] == k) {  // 타겟값 만났을 때,
      t = cnt;
      return;
  }
  if (cnt > 100) {   // 100번 넘게 갱신될 때,
      t = -1;
      return;
  }

처리 로직은 R연산, C연산의 차이가 거의 없다.

가로축이냐 세로축이냐 정도의 차이
내 구현에서는 세로축이 조금 더 복잡해 이걸 기준으로 설명하겠다.

for (int i = 0; i < SZ; i++) {
      vector<int> tmp;
      for (int j = 0; j < SZ; j++) tmp.push_back(A[j][i]);  // 아래 get_cnt에 넣기 위해 값을 복사한다.
        
      vector<int> ret = get_cnt(tmp);  // 만약 가로축 배열을 넘긴다면 그냥 A[i]와 같이 넘기면 된다.
      for (int j = 0; j < ret.size(); j++) C[j][i] = ret[j];  // 정렬 기준에 따른 값과 개수 리스트를 임시 배열에 복사

      ymax = max(ymax, (int)ret.size());  // y축을 갱신해준다.
  }

이후 원래 배열에 C 배열의 값을 복사해주면 된다.

정렬

연산자 오버로딩

bool compare(pii &a, pii &b) {
  if (a.second == b.second) return a.first < b.first;
  return a.second < b.second;
}

개수 구하기

값이 뭐가 들어있을지 모른다 100이하의 자연수… map을 써주도록 하자
map의 정렬을 위해 임시 벡터를 선언하고 값 복사 후 정렬
값과 개수를 순차적으로 return할 벡터에 넣는다.
원소의 값과 개수를 1차원 배열에 저장해 값을 그대로 붙여넣는 방식의 구현이다.

vector<int> get_cnt(vector<int> &v) {
  map<int, int> mp;
    
  for (int i = 0; i < v.size(); i++) {
      if (v[i] == 0) continue;
      mp[v[i]]++;
  }

  vector<pii> tmp(mp.begin(), mp.end());
  sort(tmp.begin(), tmp.end(), compare);

  vector<int> ret;
  for (pii nxt : tmp) {
      ret.push_back(nxt.first);
      ret.push_back(nxt.second);
  }

  return ret;
}

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int SZ = 100;
int r, c, k, t = -1;
vector<int> A[SZ], C[SZ];

bool compare(pii &a, pii &b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

vector<int> get_cnt(vector<int> &v) {
    map<int, int> mp;
    
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == 0) continue;
        mp[v[i]]++;
    }

    vector<pii> tmp(mp.begin(), mp.end());
    sort(tmp.begin(), tmp.end(), compare);

    vector<int> ret;
    for (pii nxt : tmp) {
        ret.push_back(nxt.first);
        ret.push_back(nxt.second);
    }

    return ret;
}

void solve(int cnt, int ymax, int xmax) {
    if (t != -1) return;
    if (A[r][c] == k) {
        t = cnt;
        return;
    }
    if (cnt > 100) {
        t = -1;
        return;
    }

    for (int i = 0; i < SZ; i++) {
        C[i].clear();
        C[i].assign(100, 0);
    }

    if (ymax >= xmax) {
        for (int i = 0; i < SZ; i++) {
            vector<int> ret = get_cnt(A[i]);
            for (int j = 0; j < ret.size(); j++) C[i][j] = ret[j];

            xmax = max(xmax, (int)ret.size());
        }
    }
    else {
        for (int i = 0; i < SZ; i++) {
            vector<int> tmp;
            for (int j = 0; j < SZ; j++) tmp.push_back(A[j][i]);
            
            vector<int> ret = get_cnt(tmp);
            for (int j = 0; j < ret.size(); j++) C[j][i] = ret[j];

            ymax = max(ymax, (int)ret.size());
        }
    }

    for (int i = 0; i < SZ; i++)
        for (int j = 0; j < SZ; j++)
            A[i][j] = C[i][j];

    solve(cnt + 1, ymax, xmax);

    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    for(int i=0; i<SZ; i++)
        A[i].assign(100, 0);

    cin >> r >> c >> k;
    for (int a, b, c, i = 0; i < 3; i++)
        cin >> A[i][0] >> A[i][1] >> A[i][2];

    r--, c--;

    solve(0, 3, 3);

    cout << t;
    return 0;
}

BOJ 17140. 이차원 배열과 연산

1. 문제설명

2. 알고리즘 설계

3. 전체 코드