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

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

map과 vector를 사용해서 풀었다.

 

1. row와 col 비교

row>= col이면 row따라

else 면 col따라 연산을 진행한다.

 

2. 연산

2-1. 연산을 진행할 때 등장횟수 측정을 위해 map을 사용했다. 

각 row/col마다 map으로 등장횟수를 측정하고 vector에 담아서 map을 소트했다.

vector<pair<int, int>> v(m.begin(), v.end());

 

2-2. map에 담는 과정에서 0이면 무시하고 넘어가야 하므로 

if arr[i][j] == 0이면 continue했다.

 

2-3. 한 row 혹은 col마다 연산을 진행하므로 모든 row/col의 연산이 끝난 후 다음 row와 col을 업데이트 해줘야 한다. 

row연산을 하면 col이 업데이트되고

col연산을 하면 row가 업데이트된다.

그래서 nc와 nr 변수를 만들어서 row와 col의 모든 연산이 끝난 후에 업데이트하는 식으로 구현했다.

#include <stdio.h>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int r, c, k;
int row = 3, col = 3;
int nr = 3, nc = 3;

int arr[100][100];
map<int, int> m;

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
  if (a.second == b.second)
  {
    return a.first < b.first;
  }
  return a.second < b.second;
}

void Rcal()
{
  for (int i = 0; i < row; i++)
  {
    m.clear();
    for (int j = 0; j < col; j++)
    {
      if (arr[i][j] == 0)
      {
        continue;
      }
      m[arr[i][j]]++;
      arr[i][j] = 0;
    }
    vector<pair<int, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp);

    int idx = 0;
    for (int j = 0; j < v.size(); j++)
    {
      arr[i][idx++] = v[j].first;
      arr[i][idx++] = v[j].second;
      if (idx == 100)
      {
        break;
      }
    }
    nc = max(idx, nc);
  }
  col = nc;
}

void Ccal()
{
  for (int j = 0; j < col; j++)
  {
    m.clear();
    for (int i = 0; i < row; i++)
    {
      if (arr[i][j] == 0)
      {
        continue;
      }
      m[arr[i][j]]++;
      arr[i][j] = 0;
    }
    vector<pair<int, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp);

    int idx = 0;
    for (int i = 0; i < v.size(); i++)
    {
      arr[idx++][j] = v[i].first;
      arr[idx++][j] = v[i].second;
      if (idx == 100)
      {
        break;
      }
    }
    nr = max(nr, idx);
  }
  row = nr;
}

void cal()
{
  if (row >= col)
  {
    Rcal();
  }
  else
  {
    Ccal();
  }
}

int main(void)
{
  scanf("%d%d%d", &r, &c, &k);
  r--;
  c--;

  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      scanf("%d", &arr[i][j]);
    }
  }

  int time = 0;
  while (1)
  {
    if (arr[r][c] == k)
    {
      break;
    }
    nr = 0, nc = 0;
    cal();
    time++;

    if (time == 101)
    {
      printf("-1\n");
      return 0;
    }
  }
  printf("%d\n", time);
  return 0;
}