백준 17140 : 이차원 배열과 연산

문제 링크입니다 https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

[문제내용]

 

크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

 

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다. 배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

 

 

[문제풀이]

 

[1] 입력받은 배열이 정답의 조건과 일치하면 바로 0을 출력합니다.

 

[2] 그렇지 않으면 solve() 함수를 호출하고 solve() 함수는 R 연산과 C 연산을 수행합니다.

 

[3] 행의 개수 >= 열의 개수 일 때, R 연산은 모든 행에 대해 문제의 조건에 맞게 정렬을 수행합니다.

 

- 입력받은 map을 한 행씩 확인하며 원소를 배열 arr의 인덱스로 하여 몇 번 등장했는지 기록합니다. 동시에 bool check 배열을 만들어 어떤 숫자를 발견했는지 체크해줍니다.

 

- 다시 그 행의 숫자들을 확인하며 체크된 숫자를 s 벡터에 (숫자, 등장횟수) pair 형태로 넣어줍니다. 그리고 해당 숫자의 check 배열을 false로 만듭니다(하나의 숫자를 여러 번 벡터에 넣으면 안되기 때문입니다).

 

- 벡터를 문제의 조건에 맞게 정렬한 후, 벡터의 사이즈만큼 map에 숫자, 등장횟수를 적절하게 채웁니다.

 

- map에 숫자를 채우고, 그 뒤는 0으로 채워줍니다.

 

[4] [3]과 같이 행의 개수 < 열의 개수 일 때, C 연산을 수행합니다.

 

[5] [3], [4]를 반복하며 정답을 찾았거나 100의 시간을 넘어가면 break 하고 정답을 출력합니다.

 

 

[소스코드]

 

#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAX = 100 + 10;
 
// n이라는 숫자가 m개 있음을 저장하기 위한 구조체
struct p {
    int n, m;
};
int r, c, k, map[MAX][MAX];
 
// n과 m을 인자로 받아 p type으로 묶어서 반환하는 함수
p make_p(int n, int m) {
    p temp;
 
    temp.n = n, temp.m = m;
    return temp;
}
 
// 똑같이 m개가 있으면 더 작은 숫자가 앞에 나오게
// 그렇지 않으면 등장 횟수가 작은 순서로
// 정렬하여 저장하기 위한 compare
bool comp(p a, p b) {
    if (a.m == b.m) return a.n < b.n;
    else return a.m < b.m;
}
 
// [2] R 연산과 C 연산을 조건에 맞게 수행하고 
//     map[r][c]에 들어있는 값이 k일때 최소시간을 출력하는 함수
void solve(void) {
    int R = 3, C = 3, time = 0;
    while (1) {
        // [3] 행의 개수 >= 열의 개수 : R 연산
        if (R >= C) {
 
            for (int i = 1; i <= R; i++) {
                bool check[101] = { 0, };
                int arr[101] = { 0, };
                vector <p> s;
 
                // [3] arr[4] = 5 : 4가 5번 등장
                for (int j = 1; j <= C; j++) {
                    if (!map[i][j]) continue;
                    arr[map[i][j]]++;
                    check[map[i][j]] = true;
                }
                
                // [3] check된 숫자는 벡터에 (숫자, 등장횟수)를 넣어주고
                //     check를 false로 만들어줍니다
                for (int j = 1; j <= C; j++) {
                    int temp = map[i][j];
                    if (check[temp]) {
                        s.push_back(make_p(temp, arr[temp]));
                        check[temp] = false;
                    }
                    // 이렇게 해야 똑같은 숫자를 벡터에 두 번 넣는
                    // 일이 일어나지 않습니다
                }
                sort(s.begin(), s.end(), comp);
                int idx = 1;
                // [3] 벡터의 담은 정보를 map에 채워줍니다
                for (int j = 0; j < s.size(); j++) {
                    map[i][idx++] = s[j].n;
                    map[i][idx++] = s[j].m;
                    if (idx > 100) break;
                }
                // [3] idx부터 C까지 (C가 더 클수도 작을수도 있음)
                //     0으로 채워줍니다
                for (int j = idx; j <= C; j++)
                    map[i][j] = 0;
 
                if (idx - 1 > C) C = idx - 1;
                if (C > 100) C = 100;
            }
        }
        // [4] 행의 개수 < 열의 개수 : C 연산
        else {
            for (int j = 1; j <= C; j++) {
                bool check[101] = { 0, };
                int arr[101] = { 0, };
                vector <p> s;
 
                for (int i = 1; i <= R; i++) {
                    if (!map[i][j]) continue;
                    arr[map[i][j]]++;
                    check[map[i][j]] = true;
                }
 
                for (int i = 1; i <= C; i++) {
                    int temp = map[i][j];
                    if (check[temp]) {
                        s.push_back(make_p(temp, arr[temp]));
                        check[temp] = false;
                    }
                }
                sort(s.begin(), s.end(), comp);
                int idx = 1;
                for (int i = 0; i < s.size(); i++) {
                    map[idx++][j] = s[i].n;
                    map[idx++][j] = s[i].m;
                    if (idx > 100) break;
                }
                for (int i = idx; i <= R; i++)
                    map[i][j] = 0;
 
                if (idx - 1 > R) R = idx - 1;
                if (R > 100) R = 100;
            }
        }
        time++;
        if (map[r][c] == k || time > 100) break;
    }
    // [5] 100이 넘으면 -1을 출력
    if (time > 100) printf("-1");
    else printf("%d", time);
}
 
int main(void) {
    scanf("%d%d%d", &r, &c, &k);
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            scanf("%d", &map[i][j]);
    
    // [1] 입력받은 배열이 정답이면 바로 0 출력
    if (map[r][c] == k) printf("0");
    else solve();
    return 0;
}