[프로그래머스] 행렬 테두리 회전하기(C++)

문제 URL

https://school.programmers.co.kr/learn/courses/30/lessons/77485

프로그래머스

 

[문제 설명]

행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 한다.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 하는 문제이다.

 

 

[문제 풀이]

자료구조 Map을 사용하여 위, 오른쪽, 아래, 왼쪽의 4가지 이동 방향에 따라 값을 움직여 주면 되는 문제였다. 

이때 덮어쓰기가 되기 때문에 처음 값은 따로 저장해 주어야 하며, 최솟값을 구해야 하기 때문에 이동시키는 모든 값을 비교하여 최솟값을 찾아주어야 한다.

 

[어려웠던 점]

처음에는 해시맵을 사용해서 인덱스를 key로 잡고 각 영역의 값을 계산해 주려고 했는데 회전을 여러 번 하게 되면 이웃한 영역의 값들 간 특정한 규칙이 없다는 것을 깨달았다.

---

#include <string>
#include <vector>
using namespace std;
 
int MAP[110][110];
 
int Min(int A, int B) { return A < B ? A : B; }
 
 
int Turning(int x, int y, int xx, int yy) {
    int Min_Num;
    int Temp = MAP[x][y];
    Min_Num = Temp;
    for (int i = x; i < xx; i++) {  // 왼쪽 세로 영역 이동
        Min_Num = Min(Min_Num, MAP[i][y]);
        MAP[i][y] = MAP[i + 1][y];
    }
    for (int i = y; i < yy; i++) {  // 위쪽 가로 영역 이동
        Min_Num = Min(Min_Num, MAP[xx][i]);
        MAP[xx][i] = MAP[xx][i + 1];
    }
    for (int i = xx; i > x; i--) {  // 오른쪽 세로 영역 이동 
        Min_Num = Min(Min_Num, MAP[i][yy]);
        MAP[i][yy] = MAP[i - 1][yy];
    }
    for (int i = yy; i > y; i--) {  // 아래쪽 가로 영역 이동
        Min_Num = Min(Min_Num, MAP[x][i]);
        MAP[x][i] = MAP[x][i - 1];
    }
    MAP[x][y + 1] = Temp;
    return Min_Num;
}
 
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    int Num = 1;
    
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < columns; j++) {
            MAP[i][j] = Num++;
        }
    }
    for (int i = 0; i < queries.size(); i++) {
        // Map에는 (0,0)부터 저장되어있기 때문에 각 row, col에 -1
        // (x,y)부터 (xx,yy)까지 영역이 회전
        int x = queries[i][0]; x--;
        int y = queries[i][1]; y--;
        int xx = queries[i][2]; xx--;
        int yy = queries[i][3]; yy--;
 
        answer.push_back(Turning(x, y, xx, yy));
    }
    
    return answer;
}

참고: https://yabmoons.tistory.com/676