[백준] 17406번 : 배열 돌리기 4

문제

 

---

풀이

 

예전엔 구현 문제가 정말 싫었는데 요즘은 좀 괜찮은 것 같다. 풀고나서 성취감이 커서 그런가 싶다.

 

회전의 순서는 next_permutation으로 정했다.

각 연산에 대해 s개의 정사각형이 움직이게 되는데...이걸 그림으로 표현하면

이렇게 된다.

 

제일 큰 문제가 회전일 텐데...나는 큐를 썼다. 자세한건 코드를 보면서 설명하겠다.

---

소스코드

 

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

using namespace std;

struct info {
    int idx, r, c, s;
};

vector<vector<int>> matrix;
pair<int, int> dir[4] = {{0,  1},  //우
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {-1, 0}}; //상

void rotate(int sr, int sc, int er, int ec) {
    queue<int> q;
    q.push(matrix[sr][sc]); //시작점 값
    int row = sr, col = sc + 1, d = 0; //시작점의 바로 오른쪽 좌표로 초기화
    do {
        q.push(matrix[row][col]); //값 저장
        matrix[row][col] = q.front(); //이전 위치의 값으로 업데이트
        q.pop();
        row += dir[d].first;
        col += dir[d].second;
        if ((row < sr) || (row > er) || (col < sc) || (col > ec)) { //범위를 벗어나면 위치 조정하고 방향 바꾸기
            row = row - dir[d].first + dir[(d + 1) % 4].first;
            col = col - dir[d].second + dir[(d + 1) % 4].second;
            d = (d + 1) % 4;
        }
    } while (row != sr || col != sc + 1); //원위치로 돌아올 때까지
}

int calcArr(int N, int M) { //배열의 값
    int result = 5001, tmp = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) //행의 합
            tmp += matrix[i][j];
        result = min(result, tmp); //최솟값 갱신
        tmp = 0;
    }
    return result;
}

int main() {
    int N, M, K, result = 5001;

    cin >> N >> M >> K;
    matrix.assign(N, vector<int>(M));
    vector<info> rot(K);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cin >> matrix[i][j];
    }
    for (int i = 0; i < K; i++) {
        cin >> rot[i].r >> rot[i].c >> rot[i].s;
        rot[i].idx = i; //인덱스
    }

    vector<vector<int>> tmp = matrix; //임시저장
    do {
        for (int i = 0; i < K; i++) { //회전
            for (int j = 1; j <= rot[i].s; j++) //각 회전 연산에 대해 rot[i].s개의 정사각형을 회전하게 됨
                rotate(rot[i].r - j - 1, rot[i].c - j - 1, //시작점
                       rot[i].r + j - 1, rot[i].c + j - 1); //끝점
        }
        result = min(result, calcArr(N, M)); //최솟값 갱신
        matrix = tmp; //복구
    } while (next_permutation(rot.begin(), rot.end(),
                              [](const info &i1, const info &i2) { //idx에 대해 순열
                                  return i1.idx < i2.idx;
                              }));
    cout << result;
}

원래 90줄 초반인가 그랬는데 열심히 리팩터링해서 76줄까지 줄였다. 이럴때 참 뿌듯하다.

 

struct info {
    int idx, r, c, s;
};

각 회전 연산을 저장할 구조체다. r, c, s말고 있는 idx가 뭔가 싶을텐데 순열을 위해 넣은 것이다.

 

    cin >> N >> M >> K;
    matrix.assign(N, vector<int>(M));
    vector<info> rot(K);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cin >> matrix[i][j];
    }
    for (int i = 0; i < K; i++) {
        cin >> rot[i].r >> rot[i].c >> rot[i].s;
        rot[i].idx = i; //인덱스
    }

입력을 받는 부분이다.

 

    vector<vector<int>> tmp = matrix; //임시저장

각 순열마다 배열의 상태가 달라질테니 tmp에 초기 상태를 저장한다.

 

    do {
        for (int i = 0; i < K; i++) { //회전
            for (int j = 1; j <= rot[i].s; j++) //각 회전 연산에 대해 rot[i].s개의 정사각형을 회전하게 됨
                rotate(rot[i].r - j - 1, rot[i].c - j - 1, //시작점
                       rot[i].r + j - 1, rot[i].c + j - 1); //끝점
        }
        result = min(result, calcArr(N, M)); //최솟값 갱신
        matrix = tmp; //복구
    } while (next_permutation(rot.begin(), rot.end(),
                              [](const info &i1, const info &i2) { //idx에 대해 순열
                                  return i1.idx < i2.idx;
                              }));

그리고 순열을 돌린다.

 

    while (next_permutation(rot.begin(), rot.end(),
                              [](const info &i1, const info &i2) { //idx에 대해 순열
                                  return i1.idx < i2.idx;
                              }));

구조체의 idx에 대해 오름차순 정렬을 하기 위해 이렇게 했다.

 

        for (int i = 0; i < K; i++) { //회전
            for (int j = 1; j <= rot[i].s; j++) //각 회전 연산에 대해 rot[i].s개의 정사각형을 회전하게 됨
                rotate(rot[i].r - j - 1, rot[i].c - j - 1, //시작점
                       rot[i].r + j - 1, rot[i].c + j - 1); //끝점
        }

먼저 연산의 갯수인 K개에 대해서...그리고 각 연산의 s에 대해서 2중 루프를 돈다.

rotate 함수를 보자.

 

void rotate(int sr, int sc, int er, int ec) {
    queue<int> q;
    q.push(matrix[sr][sc]); //시작점 값
    int row = sr, col = sc + 1, d = 0; //시작점의 바로 오른쪽 좌표로 초기화
    do {
        q.push(matrix[row][col]); //값 저장
        matrix[row][col] = q.front(); //이전 위치의 값으로 업데이트
        q.pop();
        row += dir[d].first;
        col += dir[d].second;
        if ((row < sr) || (row > er) || (col < sc) || (col > ec)) { //범위를 벗어나면 위치 조정하고 방향 바꾸기
            row = row - dir[d].first + dir[(d + 1) % 4].first;
            col = col - dir[d].second + dir[(d + 1) % 4].second;
            d = (d + 1) % 4;
        }
    } while (row != sr || col != sc + 1); //원위치로 돌아올 때까지
}

rotate 함수는 회전할 정사각형의 왼쪽위 좌표와 오른쪽아래 좌표를 받는다.

먼저 왼쪽위 좌표의 값을 큐에 담고 그 오른쪽 좌표부터 살펴보며

 

1. 해당 위치의 값을 큐에 담는다.

2. 해당 위치의 값을 이전 값(q.front())로 갱신한다.

 

를 반복한다.

 

        if ((row < sr) || (row > er) || (col < sc) || (col > ec)) { //범위를 벗어나면 위치 조정하고 방향 바꾸기
            row = row - dir[d].first + dir[(d + 1) % 4].first;
            col = col - dir[d].second + dir[(d + 1) % 4].second;
            d = (d + 1) % 4;
        }

범위를 벗어날 경우 방향을 바꿔주었다.

 

        result = min(result, calcArr(N, M)); //최솟값 갱신
        matrix = tmp; //복구

그런식으로 회전 연산을 끝마치면 최솟값을 갱신한다.

 

int calcArr(int N, int M) { //배열의 값
    int result = 5001, tmp = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) //행의 합
            tmp += matrix[i][j];
        result = min(result, tmp); //최솟값 갱신
        tmp = 0;
    }
    return result;
}

최솟값을 구하는 과정은 간단하다.