17140. - 이차원 배열과 연산

[URL]

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

[풀이 과정]

* 시뮬레이션

1. 1. input();
a[][]입력받는다.  최초 사이즈 3x3, Rsize = 3, Csize =3;

2. 시간 계산 while문
조건: a[r-1][c-1] ==k인가? 맞으면 시간(time) 리턴, 틀리면 계산 시작

3. 계산
우선Rsize Csize비교

 

3-1. r연산
각 행
1) calc[] 0으로 초기화
2) 열의 크기만큼 for문 돌며 calc[]배열에 1씩 증가
3) 인덱스와 배열값으로 info temp로 저장
4) info들을 벡터v에 정렬
5) 벡터v 크기만큼 for문 돌며 a_copy배열에 인덱스와 배열값으로 나열
6) maxC 계산: 다음 Csize 계산, 
7) 벡터 클리어, a_copy[][]를 a[][]로 복사, a_copy[][] 0으로 초기화

3-2. c연산
각 열
r연산 처럼 계산

 

4.

time 101초 되는순간 '-1' 출력

다른 경우, time 출력

 

 

[소스 코드]

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int r, c, k;
int a[101][101];
int a_copy[101][101] = {0, };
 
struct info {
    int val;
    int cnt;
};
 
int calc[101];
 
int Rsize, Csize;
 
bool cmp(info a, info b) {
    if (a.cnt == b.cnt)
        return a.val < b.val;
 
    else
        return a.cnt < b.cnt;
}
 
void input(){
    scanf("%d %d %d", &r, &c, &k);
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
 
    Rsize = 3;
    Csize = 3;
}
 
int main() {
 
    input();
 
    int time = 0;
 
    while (time <= 100)
    {
        if (a[r - 1][c - 1] == k)
            break;
 
        else
        {
            // 1. r 연산
            if (Rsize >= Csize)
            {
                int maxC = -1;
 
                for (int i = 0; i < Rsize; i++)
                {
                    // (r-1) calc[]배열 초기화
                    memset(calc, 0, sizeof(int) * 101);
 
                    // (r-2) 열의 크기만큼 for문 돌며 calc[]배열에 1씩 증가
                    for (int j = 0; j < Csize; j++)
                    {
                        if (a[i][j] == 0)
                            continue;
                        else
                            calc[a[i][j]]++;
                    }
 
                    vector <info> v;
                    // (r-3) 인덱스와 배열값으로 info temp로 저장
                    for (int j = 0; j < 101; j++)
                    {
                        if (calc[j] != 0)
                        {
                            info temp;
                            temp.val = j;
                            temp.cnt = calc[j];
 
                            v.push_back(temp);
                        }
                    }
                    // (r-4) info들을 벡터v에 정렬
                    sort(v.begin(), v.end(), cmp);
 
                    // (r-5) 벡터v 크기만큼 for문 돌며 a_copy배열에 인덱스와 배열값으로 나열
                    for (int j = 0; j < v.size(); j++)
                    {
                        a_copy[i][2 * j] = v[j].val;
                        a_copy[i][(2*j)+1] = v[j].cnt;
                    }
                    // (r-6) maxC 계산: 다음 Csize 계산 
                    int temp = 2*v.size();
 
                    if (maxC < temp)
                        maxC = temp;
 
                    // (r-7) 벡터 클리어, a_copy[][]를 a[][]로 복사, a_copy[][] 0으로 초기화
                    v.clear();
                }
 
                Csize = maxC;
 
                for (int i = 0; i < Rsize; i++)
                {
                    for (int j = 0; j < Csize; j++)
                    {
                        a[i][j] = a_copy[i][j];
                        a_copy[i][j] = 0;
                    }
                }
            }
 
            // 2. c 연산
            else
            {
                int maxR = -1;
 
                for (int i = 0; i < Csize; i++)
                {
                    // calc[]배열 초기화
                    memset(calc, 0, sizeof(int) * 101);
 
                    for (int j = 0; j < Rsize; j++)
                    {
                        if (a[j][i] == 0)
                            continue;
                        else
                            calc[a[j][i]]++;
                    }
 
                    vector <info> v;
 
                    for (int j = 0; j < 101; j++)
                    {
                        if (calc[j] != 0)
                        {
                            info temp;
                            temp.val = j;
                            temp.cnt = calc[j];
 
                            v.push_back(temp);
                        }
                    }
 
                    sort(v.begin(), v.end(), cmp);
 
                    for (int j = 0; j < v.size(); j++)
                    {
                        a_copy[2 * j][i] = v[j].val;
                        a_copy[(2 * j) + 1][i] = v[j].cnt;
                    }
                    int temp = 2 * v.size();
 
                    if (maxR < temp)
                        maxR = temp;
 
                    v.clear();
                }
 
                Rsize = maxR;
 
                for (int i = 0; i < Rsize; i++)
                {
                    for (int j = 0; j < Csize; j++)
                    {
                        a[i][j] = a_copy[i][j];
                        a_copy[i][j] = 0;
                    }
                }
            }
        }
 
        time++;
    }
 
    if (time == 101)
        printf("-1\n");
 
    else
        printf("%d\n", time);
 
    return 0;
}