[백준] 17140번 이차원 배열과 연산

17140번 이차원 배열과 연산

---

1. 이해하기

• 처음은 크기가 3x3인 배열로 시작한다.
• 1초가 지날때마다 배열에 연산이 적용된다.
  • R 연산: 배열의 모든 행에 대해서 정렬을 수행한다. 행의 개수 >= 열의 개수인 경우에 적용된다.
  • C 연산: 배열의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
• 정렬하는 방법은 다음과 같다.
  • 각각의 수가 몇 번 나왔는지 센다.
  • 수의 등장 횟수가 커지는 순으로, 이것이 여러가지면 수가 커지는 순으로 정렬한다.
  • 배열에 정렬된 결과를 다시 넣어준다.
  • 넣어줄때 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.
• 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
• (r,c)에 들어있는 값이 k가 되기 위한 최소 시간을 구하는 문제.
• 시뮬레이션 문제이다.

---

2. 구현하기

• R 연산과 C 연산을 각각 구현한다.

  • 이때, 배열에 들어있는 값은 100이 넘을 수 없으므로 크기 100을 가지는 배열을 이용한다.
  • 바로 원래 배열에 적용하면 배열의 크기가 줄어들었을 때 제대로 처리를 못하는 경우가 나오니 임시 배열에 바뀐 값을 적용하고 과정이 끝나면 원래 배열에 임시 배열 값을 옮긴다.

  void R(int row_cnt, int& col_cnt) {
      int next_col_cnt = 0;
      memset(temp_map,0,sizeof(temp_map));
      for(int i = 0; i < row_cnt; i++) {
          memset(temp_row,0,sizeof(temp_row));
          for(int j = 0; j < col_cnt; j++) {
              if(map[i][j] == 0) continue;
              int now = map[i][j];
              temp_row[now].num = now;
              temp_row[now].cnt++;
          }
          sort(temp_row,temp_row+101);
          int index = 0;
          for(int j = 1; j <= 100; j++) {
              if(temp_row[j].cnt == 0) continue;
              if(index >= 100) break;
              temp_map[i][index] = temp_row[j].num;
              temp_map[i][index+1] = temp_row[j].cnt;
              index+=2;
          }
          next_col_cnt = max(next_col_cnt,index);
      }
      col_cnt = next_col_cnt;
      copy_temp_to_map(row_cnt, col_cnt);
  }
  
  void C(int& row_cnt, int col_cnt) {
      int next_row_cnt = 0;
      memset(temp_map,0,sizeof(temp_map));
      for(int i = 0; i < col_cnt; i++) {
          memset(temp_col,0,sizeof(temp_col));
          for(int j = 0; j < row_cnt; j++) {
              if(map[j][i] == 0) continue;;
              int now = map[j][i];
              temp_col[now].num = now;
              temp_col[now].cnt++;
          }
          sort(temp_col,temp_col+101);
          int index = 0;
          for(int j = 1; j <= 100; j++) {
              if(temp_col[j].cnt == 0) continue;
              if(index >= 100) break;
              temp_map[index][i] = temp_col[j].num;
              temp_map[index+1][i] = temp_col[j].cnt;
              index+=2;
          }
          next_row_cnt = max(next_row_cnt,index);
      }
      row_cnt = next_row_cnt;
      copy_temp_to_map(row_cnt,col_cnt);
  }

• 초기 배열의 크기를 3x3로 설정하고 (r,c)의 값이 k가 될때까지 반복한다. 이때, 100초가 넘어가면 -1을 반환한다.

  int simulate() {
      int ret = 0;
      int row_cnt = 3, col_cnt = 3;
      while(1) {
          if(map[r][c] == k) break;
          if(ret > 100) return -1;
          if(row_cnt >= col_cnt) {
              R(row_cnt,col_cnt);
          } else {
              C(row_cnt,col_cnt);
          }
          ret++;
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct INF {
    int num,cnt;

    bool operator<(INF inf) const{
        if(cnt == inf.cnt) return num < inf.num;
        else return cnt < inf.cnt;
    }
};
int map[100][100], temp_map[100][100];
INF temp_row[101], temp_col[101];
int r,c,k;

void copy_temp_to_map(int row_cnt, int col_cnt) {
    for(int i = 0; i < row_cnt; i++) {
        for(int j = 0; j < col_cnt; j++) {
            map[i][j] = temp_map[i][j];
        }
    }
}

void R(int row_cnt, int& col_cnt) {
    int next_col_cnt = 0;
    memset(temp_map,0,sizeof(temp_map));
    for(int i = 0; i < row_cnt; i++) {
        memset(temp_row,0,sizeof(temp_row));
        for(int j = 0; j < col_cnt; j++) {
            if(map[i][j] == 0) continue;
            int now = map[i][j];
            temp_row[now].num = now;
            temp_row[now].cnt++;
        }
        sort(temp_row,temp_row+101);
        int index = 0;
        for(int j = 1; j <= 100; j++) {
            if(temp_row[j].cnt == 0) continue;
            if(index >= 100) break;
            temp_map[i][index] = temp_row[j].num;
            temp_map[i][index+1] = temp_row[j].cnt;
            index+=2;
        }
        next_col_cnt = max(next_col_cnt,index);
    }
    col_cnt = next_col_cnt;
    copy_temp_to_map(row_cnt, col_cnt);
}

void C(int& row_cnt, int col_cnt) {
    int next_row_cnt = 0;
    memset(temp_map,0,sizeof(temp_map));
    for(int i = 0; i < col_cnt; i++) {
        memset(temp_col,0,sizeof(temp_col));
        for(int j = 0; j < row_cnt; j++) {
            if(map[j][i] == 0) continue;;
            int now = map[j][i];
            temp_col[now].num = now;
            temp_col[now].cnt++;
        }
        sort(temp_col,temp_col+101);
        int index = 0;
        for(int j = 1; j <= 100; j++) {
            if(temp_col[j].cnt == 0) continue;
            if(index >= 100) break;
            temp_map[index][i] = temp_col[j].num;
            temp_map[index+1][i] = temp_col[j].cnt;
            index+=2;
        }
        next_row_cnt = max(next_row_cnt,index);
    }
    row_cnt = next_row_cnt;
    copy_temp_to_map(row_cnt,col_cnt);
}

int simulate() {
    int ret = 0;
    int row_cnt = 3, col_cnt = 3;
    while(1) {
        if(map[r][c] == k) break;
        if(ret > 100) return -1;
        if(row_cnt >= col_cnt) {
            R(row_cnt,col_cnt);
        } else {
            C(row_cnt,col_cnt);
        }
        ret++;
    }
    return ret;
}

void input() {
    cin >> r >> c >> k;
    r--; c--;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> map[i][j];
        }
    }
}

int main() {
    input();
    cout << simulate() << '\n';
    return 0;
}