[C++] 백준/BOJ - 17140 : 이차원배열과 연산

문제 이해 단계

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

3x3 배열로 시작해서 R연산과 C연산 2가지 연산이 존재한다. 

이 2가지 연산 중 한 가지 연산으로 최대 100초까지 반복한다.

행이 더 많거나 같으면 R연산, 그렇지 않으면 C연산을 한다.

R연산은 같은 행에 있는 숫자들을
(숫자, 그 숫자의 개수) 쌍으로 정리해서 나타낸다.

C연산은 같은 열에 있는 숫자들을 저런 쌍을 정리해서 나타낸다.

이런 상황에서 입력으로 r, c, k가 주어진다. 

1초마다 저런 움직임이 계속될 때,
맵에서 map [r][c] = k가 존재하는지,
존재한다면 몇 초 만에 가능한지를 구하는 문제이다.

 

---

문제 접근 단계

최우선적으로 보이는 것부터 정리해 보자면
(숫자, 그 숫자의 개수)라는 쌍이 존재한다.

이는 자료형 중에 pair로 처리해도 좋지만,
직관적으로 보기 위해 구조체로 처리해 주겠다.

struct Number{
    int num;
    int count;
};

num과 count를 통해 직관적으로 무엇을 의미하는지 보이도록 하겠다.

이 문제는 순수구현 문제로, 시키는 대로 구현만 잘하면 될 것 같은 느낌이다.

구현하기 전에 유의해야 할 점, 어떤 식으로 구현해야 할지 체크를 한번 해보자.

각각의 수가 몇 번 나왔는지 확인한 후에는 정렬을 해야 한다.

우선순위가 되어야 할 것은 수의 개수, 그다음 수 자체의 번호이다.
둘 다 오름차순이다. 그렇기 때문에 번호쌍을 만들어준 다음 항상 정렬을 해줘야 한다.

 

---

가변적인 2차원 맵

해당 2차원 맵의 특이점이라고 한다면,
각각의 행과 열의 길이가 초마다 변할 뿐만 아니라, 길이도 제각각이라는 것이다.

즉 R연산과 C연산을 구분하기 위한 행, 열 길이 계산도 복잡하다는 것이다.
행의 크기와 열의 크기가 커졌다가 작아졌다가 완전 자기 멋대로이다.

그렇기 때문에 매번 그에 적절한 행과 열의 길이를 할당해 주고,
그 안에 값을 집어넣기란 여간 귀찮은 일이 아니다.

그래서 난 이 문제의 최대 크기가 100x100이기 때문에
그냥 100x100 짜리 맵을 선언 해놓고 그 안에서 놀게 했다.

이래서 조건을 잘 활용해야 한다. 어차피 나머지는 구현 문제니까
문제 구현 단계에서 코드와 함께 설명하겠다.

 

---

문제 구현 단계

int map[101][101] = {0,}; //  맵 최대 크기

// R연산 C연산 판단함수
bool isWidth(){
    // 기본 크기인 3x3
    int height = 3;
    int width = 3;
    for(int i = 1; i <= 100; i++){
        for(int j = 1; j <= 100; j++){
            if(map[i][j] == 0) continue;
            // 가로,세로 최대 길이
            width = max(width,j);
            height = max(height,i);
        }
    }
    // 가로가 더 길면 C연산
    if(width > height) return true; 
    // 세로가 더 길거나 같으면 R연산
    else return false;
}

R연산인지 C연산인지 판단하는 isWidth함수이다.

height와 width가 3부터 시작하는 이유는
기본 입력으로 무조건 3x3이 들어오기 때문이다.

나머지는 주석을 통해 충분히 이해할 수 있을 것 같아 넘기겠다.

struct Number{
    int num;
    int count;
};

int map[101][101] = {0,}; //  맵 최대 크기
// 맵 숫자들 순서쌍으로 변환해서 담아둠
vector<vector<Number>> numbers; 

// 사용자 정렬
bool compare(Number a, Number b){
    if(a.count == b.count) return (a.num < b.num);
    return a.count < b.count;
}

// 맵 숫자들에서 순서쌍을 얻는 함수
void getNumbers(bool isWidth){
    vector<vector<Number>> arr; // numbers에 붙여넣을 변수

    if(!isWidth){
        // R연산 
        for(int i = 1; i <= 100; i++){
            vector<Number> tmp;
            unordered_set<int> select; //선택한 숫자 set
            int temp[101] = {0,};
            for(int j = 1; j <= 100; j++){
                if(map[i][j] == 0) continue;
                temp[map[i][j]]++;
                select.insert(map[i][j]);
            }
            if(select.empty()) continue;
            // 선택한 숫자들과 그 개수를 쌍으로 tmp에 넣음
            for(auto it : select) tmp.push_back({it,temp[it]});
            sort(tmp.begin(),tmp.end(),compare); // 정렬해서 넣음
            arr.push_back(tmp); // arr에 넣음
        }
    }
    else{
        // C연산
        for(int i = 1; i <= 100; i++){
            vector<Number> tmp;
            unordered_set<int> select;
            int temp[101] = {0,};
            for(int j = 1; j <= 100; j++){
                if(map[j][i] == 0) continue;
                temp[map[j][i]]++;
                select.insert(map[j][i]);
            }
            if(select.empty()) continue;
            for(auto it : select) tmp.push_back({it,temp[it]});
            sort(tmp.begin(),tmp.end(),compare);
            arr.push_back(tmp);
        }
    }
    numbers = arr; // numbers에 붙여넣음
}

핵심 함수는 맵에 있는 숫자들로부터 순서쌍을 얻는 getNumber함수이다.
매개변수로 R연산인지 C연산인지 확인하는 isWidth이다. 

맵 순서쌍을 저장해 두는 변수는 numbers이다.
getNumbers의 전체적인 로직은 다음과 같다.

숫자들의 범위가 1~100이기 때문에 temp [101]을 통해
1~100까지 배열을 만들어 각각의 값을 0으로 초기화한다.

맵을 탐색 하면서 해당 숫자가 나오면 해당 인덱스를 가진 배열을 +1 한다.
맵을 끝까지 탐색할 때까지 반복한다.

이때, select에 한 번이라도 나왔던 인덱스를 담아둔다.
그 후, select의 원소와 그 원소를 인덱스로 가진 temp배열,
즉 그 원소의 개수를 순서쌍으로 만들어 numbers에 저장한다.

이렇게 하면 순서쌍이 완성된다. 이런 방식으로 반복한다.
C연산은 똑같은 방식이지만 맵 탐색 방향이 다를 뿐이다.

// 순서쌍들을 맵에 배열
void setMap(bool isWidth){
    
    for(int i = 0; i < numbers.size(); i++){
        vector<int> arr;
        vector<Number> vec = numbers[i];
        for(int j = 0; j < vec.size(); j++){
            arr.push_back(vec[j].num); // 숫자
            arr.push_back(vec[j].count); // 개수
        }
        if(!isWidth){
            for(int j = 0; j < arr.size(); j++) map[i+1][j+1] = arr[j];
        }
        else{
            for(int j = 0; j < arr.size(); j++) map[j+1][i+1] = arr[j];
        }
    }
}

getNumbers로 만들어둔 순서쌍을 isWidth에 맞춰 맵에 배열시키는 함수이다.

순서는 숫자가 먼저 오고 그다음 개수이기 때문에 항상 이 순서대로 배열해 준다.
그리고 isWidth에 따라 C연산일 경우에는 세로로 나열될 수 있도록 한다.

핵심코드에 대한 설명은 여기서 끝이다.

이제 아래 전체 코드에 올리고, 전체 코드에 대한 설명을 조금 더 하고 끝내겠다.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <string.h>
using namespace std;

struct Number{
    int num;
    int count;
};

int map[101][101] = {0,}; //  맵 최대 크기
// 맵 숫자들 순서쌍으로 변환해서 담아둠
vector<vector<Number>> numbers; 

// 사용자 정렬
bool compare(Number a, Number b){
    if(a.count == b.count) return (a.num < b.num);
    return a.count < b.count;
}

// 맵 숫자들에서 순서쌍을 얻는 함수
void getNumbers(bool isWidth){
    vector<vector<Number>> arr; // numbers에 붙여넣을 변수

    if(!isWidth){
        // R연산 
        for(int i = 1; i <= 100; i++){
            vector<Number> tmp;
            unordered_set<int> select; //선택한 숫자 set
            int temp[101] = {0,};
            for(int j = 1; j <= 100; j++){
                if(map[i][j] == 0) continue;
                temp[map[i][j]]++;
                select.insert(map[i][j]);
            }
            if(select.empty()) continue;
            // 선택한 숫자들과 그 개수를 쌍으로 tmp에 넣음
            for(auto it : select) tmp.push_back({it,temp[it]});
            sort(tmp.begin(),tmp.end(),compare); // 정렬해서 넣음
            arr.push_back(tmp); // arr에 넣음
        }
    }
    else{
        // C연산
        for(int i = 1; i <= 100; i++){
            vector<Number> tmp;
            unordered_set<int> select;
            int temp[101] = {0,};
            for(int j = 1; j <= 100; j++){
                if(map[j][i] == 0) continue;
                temp[map[j][i]]++;
                select.insert(map[j][i]);
            }
            if(select.empty()) continue;
            for(auto it : select) tmp.push_back({it,temp[it]});
            sort(tmp.begin(),tmp.end(),compare);
            arr.push_back(tmp);
        }
    }
    numbers = arr; // numbers에 붙여넣음
}

// 순서쌍들을 맵에 배열
void setMap(bool isWidth){
    
    for(int i = 0; i < numbers.size(); i++){
        vector<int> arr;
        vector<Number> vec = numbers[i];
        for(int j = 0; j < vec.size(); j++){
            arr.push_back(vec[j].num); // 숫자
            arr.push_back(vec[j].count); // 개수
        }
        if(!isWidth){
            for(int j = 0; j < arr.size(); j++) map[i+1][j+1] = arr[j];
        }
        else{
            for(int j = 0; j < arr.size(); j++) map[j+1][i+1] = arr[j];
        }
    }
}
// R연산 C연산 판단함수
bool isWidth(){
    // 기본 크기인 3x3
    int height = 3;
    int width = 3;
    for(int i = 1; i <= 100; i++){
        for(int j = 1; j <= 100; j++){
            if(map[i][j] == 0) continue;
            // 가로,세로 최대 길이
            width = max(width,j);
            height = max(height,i);
        }
    }
    // 가로가 더 길면 C연산
    if(width > height) return true; 
    // 세로가 더 길거나 같으면 R연산
    else return false;
}

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int r,c,k;
    cin >> r >> c >> k;

    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++) cin >> map[i][j];
    
    int time = 0;
    // 100초가 넘으면 종료
    while(time <= 100){
    	// 정답 확인
        if(map[r][c] == k) {
            cout << time;
            return 0;
        }
        // 다시 R,C 연산 체크
        bool check = isWidth();
        // 맵을 받아옴 
        getNumbers(check);
        // 맵을 새로 그리도록 초기화
        memset(map,0,sizeof(map));
        setMap(check);
        time++;
    }
    cout << "-1";
}

100초가 넘어가면 실패로 간주하라고 했기 때문에
딱 100초까지만 반복해 준다.

그리고 매초마다 isWidth를 통해 R, C연산을 다시 체크해 준다.
또한 맵을 새로 그려주기 위해 맵을 초기화 한다.

 

---

시행착오

푸는데 정말 오래 걸리고, 자괴감이 정말 많이 들었다.

원래는 그냥 탐색을 진행하다가 0을 만나면
바로 탐색을 종료하도록 코드를 짰는데,
세로로 배치할 경우 중간에 0이 나올 수도 있다는 사실을 간과했다.

인터넷을 참고했는데, 그냥 단순 구현문제라고 구현만 잘하면 된다고 하니까,
그냥 내가 한심해 보이더라..

구현 문제를 아무리 풀어도 구현 실력이 느는 거 같지가 않다.
열심히 하면 잘해지는 거 맞겠지?