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

2021 Dev 매칭-벡엔드

 

2차원 좌표에서 직사각형을 정하고, 테두리를 시계방향으로 회전시키는것을 구현하는 문제이다.

완전히 구현력을 요구하는 문제이다. 삼성 A형 기출문제와 느낌이 비슷했다.

 

 

직사각형과 회전시킬 영역이 주어진다.

나는 회전을 위해서는 4개의 꼭짓점만 알면 된다고 생각했다.

그래서 주어지는 queries배열에서 4개의 꼭짓점을 추출하고, 되돌아오는 것 까지 생각해서 총 5개의 점을 vertex 벡터에 입력했다.

for(auto &q: queries){
    vector<pair<int, int> > vertex;
    vertex.push_back({q[0], q[1]});
    vertex.push_back({q[0], q[3]});
    vertex.push_back({q[2], q[3]});
    vertex.push_back({q[2], q[1]});
    vertex.push_back({q[0], q[1]});

    answer.push_back(rotateAns(vertex));
}

 

 

현재 보고있는 좌표를 replace에 넣고 시작한다.

replace는 다음 좌표를 만났을 때 해당 좌표의 값을 replace에 있는 값으로 교체해주기 위해서 임시 저장하는 장소이다.

dr, dc 배열을 만들어서 상하좌우 이동을 구현했다.

int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};

// 오른쪽 -> 아래 -> 왼쪽 -> 위
// 각 꼭짓점 좌표 필요
int rotateAns(vector<pair<int, int> > &vertex){
    int ret = 100000;
    
    int replace = Map[vertex[0].first][vertex[0].second];
    ret = min(ret, replace);
    int temp = 0;
    ...

 

 

for문을 통해 4개의 변을 모두 탐색한다는 조건을 걸고, 반복마다 각 변의 좌표를 모두 탐색하기 위해서 while문을 수행한다.

while문 에서 nr, nc값이 가장 먼저 갱신되는데, 이는 다음에 탐색할 좌표를 의미한다.

다음에 탐색할 좌표의 값을 temp에 임시 저장하고, 다음에 탐색할 좌표의 값을 replace에 있는 값으로 갱신한다.

그리고 replace는 temp값으로 갱신한다. 그리고 문제에서 요구하는 최댓값도 갱신한다.

위 순서가 중요하다. replace 변수의 정의와 위 로직을 읽어보면 어떤식으로 회전이 구현되는지 알 수 있을것이다.

for(int i = 0; i < vertex.size() - 1; i++){
    int nr = vertex[i].first;
    int nc = vertex[i].second;

    while(true){
        nr += dr[i];
        nc += dc[i];
        temp = Map[nr][nc];

        Map[nr][nc] = replace;
        replace = temp;
        ret = min(ret, replace);
       
       ...

 

다음 좌표가 꼭짓점이라면(다음 좌표의 값도 갱신해준 상태) while문을 종료한다.

if(nr == vertex[i+1].first && nc == vertex[i+1].second) break;

처음에 꼭짓점을 5개(시작점을 2번 포함)를 vector에 넣은 이유는 시작점으로 되돌아 오는것을 구현하기 위해서이다.

 

 

 

 

전체 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;


int Map[101][101];
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};

// 오른쪽 -> 아래 -> 왼쪽 -> 위
// 각 꼭짓점 좌표 필요
int rotateAns(vector<pair<int, int> > &vertex){
    int ret = 100000;
    
    int replace = Map[vertex[0].first][vertex[0].second];
    ret = min(ret, replace);
    int temp = 0;
    
    for(int i = 0; i < vertex.size() - 1; i++){
        int nr = vertex[i].first;
        int nc = vertex[i].second;
        
        while(true){
            nr += dr[i];
            nc += dc[i];
            temp = Map[nr][nc];
            
            Map[nr][nc] = replace;
            replace = temp;
            ret = min(ret, replace);
            if(nr == vertex[i+1].first && nc == vertex[i+1].second) break;
        }
    }
    
    return ret;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    
    int num = 1;
    for(int i = 1; i <= rows; i++){
        for(int j = 1; j <= columns; j++){
            Map[i][j] = num++;
        }
    }
    
    for(auto &q: queries){
        vector<pair<int, int> > vertex;
        vertex.push_back({q[0], q[1]});
        vertex.push_back({q[0], q[3]});
        vertex.push_back({q[2], q[3]});
        vertex.push_back({q[2], q[1]});
        vertex.push_back({q[0], q[1]});
        
        answer.push_back(rotateAns(vertex));
    }
    
    
    return answer;
}