[C++] 백준 16935 - 배열 돌리기 3

---

문제 이해 단계

 

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

 

문제 자체는 배열을 뒤집고 돌리고,
4분할해서 분할끼리 또 돌리고 하는 거라 이해하는 건 간단하다.

로직이 같고 방향이 다른 것으로만 쳐도 구현해야 하는 것만 3개이다.

일단 입력의 제한사항으로는 배열의 크기 NxM이 입력으로 들어오고 각각 N과 M은 100 이하의 짝수이다.
그리고 4 분할할 때의 중심은 N/2, M/2이다.

또 다른 입력으로 주어지는 R은 명령어의 횟수를 뜻한다.

이게 1000개까지 가능하다는 것은
똑같은 입력이 여러 번 들어올 수도 있는 경우도 생각해야 한다는 것이다.

 

 

---

문제 접근 단계

해당 문제가 일반적인 배열 돌리기랑 다른 점은, 정사각형이 아닌 직사각형이라는 것이다.
이건 90도씩 돌릴 때마다 가로 세로의 길이가 달라진다.

즉, 가로 세로 길이가 NxM 고정이 아니라는 것이다.
구현을 할 때 이 점을 항상 유의하면서 구현을 해야 한다.

이 문제는 진짜 쌩 구현 문제이고, 배열 인덱스를 통해 자리를 바꿔주는 문제이다.

따라서 문제 접근 단계에서 코드 없이 설명하는 것보다는,
밑에 코드와 함께 좀 더 자세히 설명하는 것이 훨씬 낫다.

그래서 문제 접근 단계에서 위에서 말했던 가로, 세로 길이가 고정이 아니라는 점만 가져가면 될 것 같다.

 

 

---

문제 구현 단계

---

상하, 좌우 반전 구현

int N,M;
int map[101][101];
bool check = true;

// 상하,좌우 반전 함수( kind 상하,좌우 구분)
void flip(int kind){

    // 가로와 세로의 현재 상태를 체크해서 갱신해줌 ----
    int real_N = N;
    int real_M = M;
    if(!check){
        real_M = N;
        real_N = M;
    }
    // --------------------------------------

    // 상하반전
    if(kind == 1){
        // 가로가 아닌 세로로 탐색
        for(int i = 0; i < real_M; i++){
            // 줄에서의 반복은 딱 절반만 하면 됨
            for(int j = 0; j < real_N/2; j++){

                // 두 자리의 값을 바꿈 
                int tmp = map[j][i];
                // 행 탐색(세로로 탐색)
                map[j][i] = map[real_N-j-1][i];
                map[real_N-j-1][i] = tmp;
            }
        }
    }
    // 좌우반전
    else{
        // 가로로 탐색
        for(int i = 0; i < real_N; i++){
            for(int j = 0; j < real_M/2; j++){
                int tmp = map[i][j];
                // 가로로 탐색
                map[i][j] = map[i][real_M-j-1];
                map[i][real_M-j-1] = tmp;
            }
        }
    }
}

kind를 통해 상하 반전과 좌우 반전을 구분해 준다.

check는 현재 배열의 상태를 나타내기 위해서 만들어둔 임의의 값이다.
true라면 가로-세로가 NxM, false라면 MxN을 뜻한다.

이런 식으로 유동적으로 바뀌는 가로 세로를 갱신해 주었다.

상하와 좌우를 반전해 주는 로직은 둘 다 비슷하다.
상하반전은 탐색을 위에서 아래로(세로 방향)으로 해주고,
좌우반전은 탐색을 왼쪽에서 오른쪽(가로 방향)으로 한다.

그렇게 현재 탐색하는 인덱스와 반전되는 부분 그러니까 대칭되는 부분과 바꾼다.
대칭되는 부분과 바꾸는 것이기 때문에 반복 횟수를 절반으로 줄인다.
(절반으로 줄이지 않으면 원래 배열로 돌아온다)

 

---

시계/ 반시계 방향 90도 돌리기 구현

void rotate(int kind){

    int temp[101][101] = {0,}; // 90도 돌린 새로운 배열
    fill(&temp[0][0],&temp[101-1][101],0); // temp 초기화

    // 배열 현재 상태 체크
    if(check){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                // 시계 방향
                if(kind == 3) temp[j][N-1-i] = map[i][j];
                // 반시계 방향
                else temp[M-1-j][i] = map[i][j];
            }
        }
        check = false; // 돌렸으니 상태도 변경
    }
    else{
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                // 시계 방향
                if(kind == 3) temp[j][M-1-i] = map[i][j];
                // 반시계 방향
                else temp[N-1-j][i] = map[i][j];
            }
        }
        check = true; // 돌렸으니 상태도 변경
    }
    fill(&map[0][0],&map[101-1][101],0); // map 값 다 0으로 만듬

    // 새롭게 만들어진 temp를 map에 넣음으로써 map 갱신
    for(int i = 0; i < 101; i++)
        for(int j = 0; j < 101; j++) map[i][j] = temp[i][j];
}

시계/반시계 방향으로 90도씩 돌리는 함수이다.
이 역시 kind를 통해 방향을 구분한다.

사이즈를 위한 check를 확인도 중요하지만,
해당 행동은 직접적으로 배열을 돌리는 것이기 때문에 가로 세로를 바꾼다.

그래서 돌린 후에는 이 check를 바꿔줘야 한다.
돌리는 아이디어는 그림으로 설명하겠다.

중앙은 우리가 일반적으로 탐색하는 방향이다.
1~24까지 순서대로 탐색한다. 그리고 이 번호가 배열의 번호라고 생각해 보자.

각각 시계/반시계로 돌리면 해당 그림처럼 될 것이다.

저렇게 중앙에 같은 열에 있는 것을 묶어보자.
그러면 어느 정도 규칙이 보이는 것을 확인할 수 있다.

위에서 시계/반시계로 돌리는 것은 해당 방법을 사용한 것이다.

배열을 돌린 값을 새로 만든 배열 temp에 저장한다.
그리고 map을 초기화한 이후, temp를 map에 넣음으로써 완성시킨다.

 

---

분할하여 반시계/시계방향 돌리기

void divided(int kind){

    // 가로와 세로의 현재 상태를 체크해서 갱신해줌 ----
    int real_N = N;
    int real_M = M;
    if(!check){
        real_M = N;
        real_N = M;
    }
    // ---------------------------------------

    int width = real_M/2; // 자르는 가로 기준(절반)
    int height = real_N/2;// 자르는 세로 기준(절반)

    vector<vector<int>> v[2][2]; // 각각 4분할로 담을 배열 벡터
    //4분할
    for(int i = 0; i < real_N; i++){
        vector<int> tmp;
        // 열의 절반까지만 한 배열
        for(int j = 0; j < real_M/2; j++){
            tmp.push_back(map[i][j]);
        }
        v[i/height][0].push_back(tmp);
        tmp.clear();

        // 남은 열의 절반 배열 다른 배열에 담음
        for(int j = real_M/2; j < real_M; j++){
            tmp.push_back(map[i][j]);
        }
        v[i/height][1].push_back(tmp);
    }

    vector<vector<int>> tmp = v[0][0];
    // 시계 방향으로 돌림
    if(kind == 5){
        v[0][0] = v[1][0];
        v[1][0] = v[1][1];
        v[1][1] = v[0][1];
        v[0][1] = tmp;
    }

    // 반시계 방향으로 돌림
    else{
        vector<vector<int>> tmp = v[0][0];
        v[0][0] = v[0][1];
        v[0][1] = v[1][1];
        v[1][1] = v[1][0];
        v[1][0] = tmp;
    }

    for(int i = 0; i < real_N; i++){
        for(int j = 0; j < real_M; j++){
            //(i/height)*height : 배열 인덱스를 구하기 위한 오프셋
            map[i][j] = v[i/height][j/width][i-(i/height)*height][j-(j/width)*width];
        }
    }
}

사분할을 위해 전체 배열의 가로와 세로 길이를 구해주고, 분할을 담아줄 벡터를 만들어줬다.

각각의 위치를 구분해 주기 위해 2차원 배열로
[0][0], [0][1], [1][0], [1][1] 4개로 나타냈다.

가로와 세로 길이를 각각 절반으로 잘라줘서 그만큼 다른 벡터에 담고
kind의 값에 따라 값을 시계/반시계 방향으로 돌린다.

4차원 배열은 좀 복잡한데,
그냥 4 분할해서 담아뒀던 벡터에 들어있던 값을 모두 다시 맵 배열에 넣어주는 것이다.

그래서 그 오프셋을 맞혀주기 위해 (i/hieght)*height 같은 작업을 해주는 것이다.

이제 모든 함수에 대한 설명은 여기까지고 나머지는 전체 코드에 대해 올리고 끝내겠다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N,M;
int map[101][101];
bool check = true;

// 상하,좌우 반전 함수( kind 상하,좌우 구분)
void flip(int kind){

    // 가로와 세로의 현재 상태를 체크해서 갱신해줌 ----
    int real_N = N;
    int real_M = M;
    if(!check){
        real_M = N;
        real_N = M;
    }
    // --------------------------------------

    // 상하반전
    if(kind == 1){
        // 가로가 아닌 세로로 탐색
        for(int i = 0; i < real_M; i++){
            // 줄에서의 반복은 딱 절반만 하면 됨
            for(int j = 0; j < real_N/2; j++){

                // 두 자리의 값을 바꿈 
                int tmp = map[j][i];
                // 행 탐색(세로로 탐색)
                map[j][i] = map[real_N-j-1][i];
                map[real_N-j-1][i] = tmp;
            }
        }
    }
    // 좌우반전
    else{
        // 가로로 탐색
        for(int i = 0; i < real_N; i++){
            for(int j = 0; j < real_M/2; j++){
                int tmp = map[i][j];
                // 가로로 탐색
                map[i][j] = map[i][real_M-j-1];
                map[i][real_M-j-1] = tmp;
            }
        }
    }
}


void rotate(int kind){

    int temp[101][101] = {0,}; // 90도 돌린 새로운 배열
    fill(&temp[0][0],&temp[101-1][101],0); // temp 초기화

    // 배열 현재 상태 체크
    if(check){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                // 시계 방향
                if(kind == 3) temp[j][N-1-i] = map[i][j];
                // 반시계 방향
                else temp[M-1-j][i] = map[i][j];
            }
        }
        check = false; // 돌렸으니 상태도 변경
    }
    else{
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                // 시계 방향
                if(kind == 3) temp[j][M-1-i] = map[i][j];
                // 반시계 방향
                else temp[N-1-j][i] = map[i][j];
            }
        }
        check = true; // 돌렸으니 상태도 변경
    }
    fill(&map[0][0],&map[101-1][101],0); // map 값 다 0으로 만듬

    // 새롭게 만들어진 temp를 map에 넣음으로써 map 갱신
    for(int i = 0; i < 101; i++)
        for(int j = 0; j < 101; j++) map[i][j] = temp[i][j];
}
void divided(int kind){

    // 가로와 세로의 현재 상태를 체크해서 갱신해줌 ----
    int real_N = N;
    int real_M = M;
    if(!check){
        real_M = N;
        real_N = M;
    }
    // ---------------------------------------

    int width = real_M/2; // 자르는 가로 기준(절반)
    int height = real_N/2;// 자르는 세로 기준(절반)

    vector<vector<int>> v[2][2]; // 각각 4분할로 담을 배열 벡터
    //4분할
    for(int i = 0; i < real_N; i++){
        vector<int> tmp;
        // 열의 절반까지만 한 배열
        for(int j = 0; j < real_M/2; j++){
            tmp.push_back(map[i][j]);
        }
        v[i/height][0].push_back(tmp);
        tmp.clear();

        // 남은 열의 절반 배열 다른 배열에 담음
        for(int j = real_M/2; j < real_M; j++){
            tmp.push_back(map[i][j]);
        }
        v[i/height][1].push_back(tmp);
    }

    vector<vector<int>> tmp = v[0][0];
    // 시계 방향으로 돌림
    if(kind == 5){
        v[0][0] = v[1][0];
        v[1][0] = v[1][1];
        v[1][1] = v[0][1];
        v[0][1] = tmp;
    }

    // 반시계 방향으로 돌림
    else{
        vector<vector<int>> tmp = v[0][0];
        v[0][0] = v[0][1];
        v[0][1] = v[1][1];
        v[1][1] = v[1][0];
        v[1][0] = tmp;
    }

    for(int i = 0; i < real_N; i++){
        for(int j = 0; j < real_M; j++){
            //(i/height)*height : 배열 인덱스를 구하기 위한 오프셋
            map[i][j] = v[i/height][j/width][i-(i/height)*height][j-(j/width)*width];
        }
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int R;
    cin >> N >> M >> R;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) cin >> map[i][j];

    while(R--){
        int num;
        cin >> num;
        switch(num){
            case 1:
            case 2:
            flip(num);
            break;

            case 3:
            case 4:
            rotate(num);
            break;

            case 5:
            case 6:
            divided(num);
            break;
        }
    }
    int size = max(N,M);
    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            if(map[i][j] == 0) continue;
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

 

 

---

시행착오

구현을 여러 개 해야 돼서 엄청나게 귀찮은 문제였다. 게다가 구현이 그렇게 쉽지도 않았다.

풀아봤던 모든 배열 돌리기 문제는 정사각형이어서 이렇게 고생하진 않았는데,
이렇게 직사각형을 돌려보는 것은 처음이다.

푸는데 한 4시간은 걸린 것 같다.
실버 1 문제이지만 알차게 모든 교육적인 요소가 다 들어가 있는 것 같다.

근데 다시 풀긴 싫다.