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

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

어려운 구현 문제였습니다. (다시 풀기)

1. 현재 행에서 각 열의 숫자가 나오는 빈도 수를 구합니다. (cnt 배열 이용)

2. cnt 배열의 값이 0 이상인 경우, 숫자와 그 빈도 수를 저장합니다. (pair형 2차원 벡터 v 이용)

3. 초기 입력 배열 A를 0으로 초기화하고, v 벡터를 빈도 수, 크기 순으로 오름차순 정렬합니다. (이를 쉽게 하기 위해서 v에 값을 넣을 때 빈도 수를 first, 숫자를 second로 넣었음)

4. 정렬된 v의 요소들을 A에 다시 넣어주고, 그 과정에서 열의 크기를 갱신합니다.

6. 변형된 배열을 토대로, 종료 조건을 만족하면 종료하고, 아니라면 열 연산을 위와 비슷한 방법으로 진행합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int A[101][101], R = 3, C = 3;
int r, c, k, answer;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c >> k;
    --r;
    --c;
    
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            cin >> A[i][j];
        }
    }
    
    while(1) {
        if(A[r][c] == k) break;
        
        answer++;
        if(answer > 100) {
            answer = -1;
            break;
        }
        
        vector<pair<int, int > > v[101]; // (숫자, 숫자의 빈도수) pair가 저장될 2차원 배열
        
        // 행 연산
        if(R >= C) {
            for(int i = 0; i < R; i++) {
                int cnt[101] = {0, }; // 현재 행에서 각 열의 숫자가 나오는 빈도수 확인
                for(int j = 0; j < C; j++) {
                    if(A[i][j] > 0) cnt[A[i][j]]++;
                }
                
                for(int j = 1; j <= 100; j++) {
                    if(cnt[j] > 0) v[i].push_back({ cnt[j], j }); // 빈도수, 숫자
                }
            }
            
            // 배열 초기화
            for(int i = 0; i < R; i++) {
                for(int j = 0; j < C; j++) {
                    A[i][j] = 0;
                }
            }
            
            // 빈도수, 크기 순으로 오름차순 정렬
            for(int i = 0; i < R; i++) {
                sort(v[i].begin(), v[i].end());
            }
            
            // 2차원 배열의 내용을 A에 넣어 배열의 형태 변경
            for(int i = 0; i < R; i++) {
                int tmp = 0; // 갱신될 열의 크기
                for(int j = 0; j < v[i].size(); j++) {
                    A[i][tmp++] = v[i][j].second; // 숫자
                    A[i][tmp++] = v[i][j].first; // 빈도수
                }
                C = max(C, tmp); // 열의 크기 갱신
            }
        
        // 열 연산
        } else {
            for(int i = 0; i < C; i++) {
                int cnt[101] = {0, };
                for(int j = 0; j < R; j++) {
                    if(A[j][i] > 0) cnt[A[j][i]]++;
                }
                
                for(int j = 1; j <= 100; j++) {
                    if(cnt[j] > 0) v[i].push_back({ cnt[j], j });
                }
            }
            
            for(int i = 0; i < C; i++) {
                for(int j = 0; j < R; j++) {
                    A[j][i] = 0;
                }
            }
            
            for(int i = 0; i < C; i++) {
                sort(v[i].begin(), v[i].end());
            }
            
            for(int i = 0; i < C; i++) {
                int tmp = 0;
                for(int j = 0; j < v[i].size(); j++) {
                    A[tmp++][i] = v[i][j].second;
                    A[tmp++][i] = v[i][j].first;
                }
                R = max(R, tmp);
            }
        }
    }
    
    cout << answer;
}