[ 백준 17140 ] 이차원 배열과 연산 (C++)

백준의 이차원 배열과 연산(17140) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제를 하나하나 해결해 나가보도록 하자.

    사실상, R연산이든 C연산이든 서로 풀이법이 똑같고 Index접근만 다르기 때문에 R연산을 토대로 설명을 진행하겠다.

    먼저 초기에는 무조건 3x3 짜리 행렬이 입력으로 들어오게 된다. 이 경우 R연산을 진행하게 된다.

    진행과정은 이렇다.

    1. 각 행에서 존재하는 숫자의 갯수 Count 해주기

    2. Count해준 숫자의 갯수와 숫자를 Vector에 넣기.

    3. 정렬 후, MAP에 입력해주기.

    4. 최대 Size 알아내기.

    먼저 각 행에서 존재하는 숫자의 갯수를 Count해줘야 한다.

    예를 들어서, [ 1 2 1 ] 이 있으면 이를 Count할 경우 1 = 2 , 2 = 1개로 될 것이다.

    이를 문제에 조건에 맞게 만들면 [ 2 1 1 2 ] 가 된다. 즉, 갯수가 작은 놈이 앞에오고 그 놈이 여러개라면 숫자가 작은것이

    더 앞에 오게 된다.

    이를 위해서 본인은 이 숫자들을 pair로 vector에 넣어주었다. 즉, [ 1 2 1 ] 에서 숫자의 갯수를 Count후 Vector에 넣어주게

    되면 다음과 같이 될 것이다. vector<pair<int,int>> V = { pair(2 , 1) , pair(1 , 2) } 와 같이 될 것이다.

    위의 pair의 순서는 바로 (갯수, 숫자) 이다. 굳이 (숫자, 갯수)가 아닌(갯수, 숫자)로 값을 넣어준 이유는 '정렬' 때문이다.

    vector의 pair를 sort함수를 통해서 정렬할 경우, 앞의 데이터들을 오름차순으로 먼저 정렬하고, 만약 앞의 데이터가

    같다면 두번째 데이터들을 기준으로 오름차순으로 정렬을 해주기 때문이다.

    사실, sort기준을 본인이 직접 만들어서 해도 됬었지만 굳이 그렇게 하지 않았다.

    즉, 저렇게 값을 pair로 넣어준 후 정렬을 시켜주면, "갯수가 적은 숫자가 앞으로 우선적으로 오고 그 값이 여러개라면 더

    작은 숫자가 앞으로 온다".

    이렇게 vector에 저장되 있는 값을 이제는 MAP에 입력만 해주면 된다. 그 전에 해당 행의 모든 값들을 0으로 바꿔주자.

    그냥 숫자를 덮어씌우지 않고 0으로 먼저 바꿔주는 이유는, 기존의 숫자가 더 길 수도 있기 때문이다.

    예를 들어서 [ 1 2 2 3 3 1 ] 에 [ 2 1 1 2 ] 를 집어넣을 경우, [ 3 1 ] 이 그대로 남아있을 수 있기 때문이다.

    마지막으로는 최대 Size를 알아내야 하는 것이다.

    최대 Size는 따로 계산해 주지 않았다. 왜냐하면 이 전 과정인 Vector에 있는 값들을 MAP에 입력하면서 알아낼 수 있기

    때문이다.

    [ 1 2 2 1 ]을 넣게 되면 결국 크기가 4가 된다. 우리는 MAP에 값을 넣을 때 Index값만 계산을 한다면 Size는 자동적으로

    알 수가 있기 때문이다.

    최종적으로 모든 Size를 다 구한 후, 오름차순으로 정렬 후 가장 마지막값을 최대 길이로 가지면 된다.

    이게 R 연산이다.

   

    사실 C연산도 똑같다. 단지 행과 열을 바꿔서 계산만 하면 될 뿐이다. 따라서 C연산에 대한 별도의 설명은 하지 않겠다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
int R, C, K, Answer;
int MAP[MAX][MAX];
int Number_Cnt[MAX];
 
void Input()
{
    cin >> R >> C >> K;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Print()
{
    for (int i = 1; i < 50; i++)
    {
        for (int j = 1; j < 50; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
    cout << "########################################" << endl;
}
 
void Find()
{
    int Time = 0;
    int Hang = 3;
    int Yul = 3;
 
    while (1)
    {
        if (MAP[R][C] == K) { Answer = Time; break; }
        if (Time > 100) { Answer = -1; break; }
 
        vector<int> Size;
        if (Hang >= Yul)    // 정사각형이거나 세로로긴 형태
        {
            for (int i = 1; i <= Hang; i++)
            {
                vector<pair<int, int>> V;
                memset(Number_Cnt, 0, sizeof(Number_Cnt));
                for (int j = 1; j <= Yul; j++) Number_Cnt[MAP[i][j]]++;
                for (int j = 1; j < MAX; j++)
                {
                    if (Number_Cnt[j] == 0) continue;
                    V.push_back(make_pair(Number_Cnt[j], j));
                }
                sort(V.begin(), V.end());
                for (int j = 1; j <= Yul; j++) MAP[i][j] = 0;
                int Idx = 1;
                for (int j = 0; j < V.size(); j++)
                {
                    MAP[i][Idx++] = V[j].second;
                    MAP[i][Idx++] = V[j].first;
                }
                Idx--;
                Size.push_back(Idx);
            }
            sort(Size.begin(), Size.end());
            Yul = Size.back();
        }
        else        // 가로로 더 긴꼴
        {
            for (int i = 1; i <= Yul; i++)
            {
                vector<pair<int, int>> V;
                memset(Number_Cnt, 0, sizeof(Number_Cnt));
                for (int j = 1; j <= Hang; j++) Number_Cnt[MAP[j][i]]++;
                for (int j = 1; j < MAX; j++)
                {
                    if (Number_Cnt[j] != 0)
                    {
                        V.push_back(make_pair(Number_Cnt[j], j));
                    }
                }
                sort(V.begin(), V.end());
                for (int j = 1; j <= Hang; j++) MAP[j][i] = 0;
                int Idx = 1;
                for (int j = 0; j < V.size(); j++)
                {
                    MAP[Idx++][i] = V[j].second;
                    MAP[Idx++][i] = V[j].first;
                }
                Idx--;
                Size.push_back(Idx);
            }
            sort(Size.begin(), Size.end());
            Hang = Size.back();
        }
        Time++;
    }
}
 
void Solution()
{
    if (MAP[R][C] == K)
    {
        Answer = 0;
        cout << Answer << endl;
        return;
    }
    Find();
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}