Programmers: 행렬 테두리 회전

문제

• https://programmers.co.kr/learn/courses/30/lessons/77485
• 분류: 큐?

문제 설명

• 시작점 [x1, y1]과 끝점[x2, y2]가 주어지면
• 그 범위에 해당하는 행렬의 테두리[만]을 시계방향으로 한번씩 회전하면 됨

접근

• 큐에다가 바꿔야 되는 수를 차례대로 넣고
• 한칸씩 밀어서 넣으면 끝!
  
• [x1, y1, x2, y2] = [2, 2, 5, 4] 일 때
• 큐는
  8, 9, 10, 16, 22, 28, 27, 26, 20, 14
  형태로 존재
• 현재 9가 있는 자리에서 큐에 있는 내용을 덮어쓰기 시작함
  • 그래서 그림에 있는 9가 8로 바뀌고 10이 9로 바뀌고 ~~

알고리즘

• 범위에 해당하는 테두리를 큐에 삽입
  • 삽입하면서 수 중에 가장 작은 수를 찾기
• 큐에 있는 내용을 한칸씩 밀어서 행렬에 적용
• 가장 작은 수를 answer 벡터에 삽입
• 반복

코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <climits>

using namespace std;

void print_vector(vector<vector<int>>& target_vector) {
    for (vector<int> tmp_vector : target_vector) {
        for (int tmp : tmp_vector) {
            cout << tmp << " ";
        }
        cout << endl;
    }
}

vector<vector<int>> get_matrix(int rows, int columns) {
    vector<vector<int>> ret_val(rows, vector<int>(columns));
    int counter = 1;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            ret_val[i][j] = counter;
            counter++;
        }
    }

    return ret_val;
}

queue<int> traverse_and_queue(vector<vector<int>>& matrix, vector<int>& query, int& min_num) {
    int x1 = query[0]-1;
    int y1 = query[1]-1;
    int x2 = query[2]-1;
    int y2 = query[3]-1;

    queue<int> list;

    // Top X
    for (int i = y1; i < y2; i++) {
        min_num = min(min_num, matrix[x1][i]);
        list.push(matrix[x1][i]);
    }

    // Rightmost
    for (int i = x1; i < x2; i++) {
        min_num = min(min_num, matrix[i][y2]);
        list.push(matrix[i][y2]);
    }

    // Bottom
    for (int i = y2; i >= y1; i--) {
        min_num = min(min_num, matrix[x2][i]);
        list.push(matrix[x2][i]);
    }

    // Leftmost
    for (int i = x2-1; i >= x1+1; i--) {
        min_num = min(min_num, matrix[i][y1]);
        list.push(matrix[i][y1]);
    }

    return list;
}

int manipulate_matrix(vector<vector<int>>& matrix, vector<int>& query) {
    int x1 = query[0]-1;
    int y1 = query[1]-1;
    int x2 = query[2]-1;
    int y2 = query[3]-1;
    int min_num = INT_MAX;
    queue<int> list = traverse_and_queue(matrix, query, min_num);

    // Top X
    for (int i = y1+1; i < y2; i++) {
        matrix[x1][i] = list.front(); list.pop();
    }

    // RightMost
    for (int i = x1; i < x2; i++) {
        matrix[i][y2] = list.front(); list.pop();
    }

    // Bottom
    for (int i = y2; i > y1; i--) {
        matrix[x2][i] = list.front(); list.pop();
    }

    // LeftMost
    for (int i = x2; i >= x1; i--) {
        matrix[i][y1] = list.front(); list.pop();
    }

    return min_num;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    vector<vector<int>> matrix = get_matrix(rows, columns);
    for (vector<int> each_query : queries) {
        answer.push_back(manipulate_matrix(matrix, each_query));
    }

    return answer;
}