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

프로그래머스의 행렬 테두리 회전하기(Lv2) 문제이다.

 

[ 문제풀이 ]

주어진 범위의 사각형을 돌렸을 때, 회전 한 사각형에서의 최솟값들을 구해야 하는 문제이다.

 

#1. 회전하기

이 문제에서 구현해야할 거의 전부이자 핵심인 부분이다. 바로 주어진 범위의 사각형을 회전시키는 것이다.

항상 말하지만, 회전하는 것과 같이 주어진 인덱스 번호를 가지고 놀아야 하는 과정은 특별한 알고리즘과 자료구조가 사용되는 것이 아니기 때문에, 자기가 가장 편하다고 생각하는 방법으로 구현하는 것을 권장한다.

이 글에서는, 본인이 구현한 방법에 대해서 소개할 것이다.

 

먼저, 하나 주의해야할 사항에 대해서부터 이야기를 해보자.

만약, 우리가 회전해야 하는 사각형이 "정사각형" 이였다면, 본인은 보통 한 변을 기준으로 회전을 시킨다.

즉 ! 정사각형에 있는 데이터들을 하나하나씩 옮기는 것이 아니라, 한 변에 있는 데이터들을 다른 변으로 옮기는 방식으로 구현을 한다. 하지만 ! 이 문제 같은 경우에는 "직사각형" 또한 발생할 수 있기 때문에, 이렇게 하나의 변을 기준으로 잡고 옮겨 버리게 되면 제대로 회전 되지 않을 수가 있다.

따라서 이 경우에는 데이터 하나하나씩을 옮겨주는 방식으로 구현을 하였다.

 

간단하게, 우리가 회전해야 하는 사각형의 가장 왼쪽 상단의 좌표를 (x , y)로, 그리고 가장 우측 하단의 좌표를 (xx , yy)라고 가정해보자. 그리고 이 좌표들을 통해서 회전을 시켜보자.

위의 그림에서 회색으로 칠해진 사각형이 우리가 회전해야 하는 사각형이고, 빨간점이 (x , y) 파란점이 (xx, yy) 인 것이다.

그럼 한 변씩 진행해보자.

먼저, 가장 왼쪽에 있는 변을 생각을 해보자.

간단하게, 좌표들을 'A', 'B', 'C'라고 표현을 했을 때, A는 빨간점으로, B는 A로, C는 B로 가야 한다.

그럼, A, B, C를 (x , y)를 이용해서 표현을 해보자.

A = (x + 1 , y)

B = (x + 2 , y)

C = (x + 3 , y) 가 될 것이다.

즉 ! (x + 1 , y)에 있는 데이터는 (x , y)로 가야하고, (x + 2 , y)에 있는 데이터는 (x + 1 , y)로 가야한다.

이 부분을 간단하게 코드로 구현한다면 다음과 같이 구현할 수 있다.

for(int i = x ; i < xx ; i++)
{
	MAP[i][y] = MAP[i + 1][y];
}

 

그 다음 변으로 넘어가보자.

B는 A로, 파랑점은 B로 가야 하는 상황이다.

이를 또 각각 좌표로 표현해보자.

A = (xx , y)

B = (xx , y + 1)

C = (xx , y + 2) 로 표현을 할 수 있다.

즉 ! (xx , y + K)에 있는 데이터가 (xx , y + K - 1)로 가야 하는 것이다. 이를 코드로 나타내면 다음과 같다.

for(int i = y; i < yy; i++)
{
	MAP[xx][i] = MAP[xx][i + 1];
}

 

나머지 두 변도 마찬가지이다. 이런식으로, 좌표를 하나하나씩 옮기는 것처럼 구현을 해본다면 다음과 같이 구현을 할 수 있다.

(똑같은 원리이기 때문에, 더 이상의 설명은 생략하겠다.)

/* 가장 오른쪽 변에 대한 계산 */
for (int i = xx; i > x; i--)
{
	MAP[i][yy] = MAP[i - 1][yy];
}

/* 가장 윗쪽 변에 대한 계산 */
for (int i = yy; i > y; i--)
{
	MAP[x][i] = MAP[x][i - 1];
}

 

그런데 주의해야 할 점이 하나 있다 ! 위의 코드에서 잘못된 부분은 없지만, 위의 코드를 순차적으로 실행한다면, 딱 하나의 데이터만 잘못된 데이터처럼 회전이 될 것이다.

바로 빨간점이 찍힌 데이터만이 잘못된 값이 저장될 것이다. 왜그럴까 ???

회전을 시켰을 때, 빨강색 점에 저장되는 값은 바로 왼쪽에 있는 (x , y)의 값이 될 것이다.

그럼, 초기의 (x , y)의 값이 'K' 라고 가정해보자.

그리고 위의 과정을 순차적으로 진행시키게 되면, 가장 왼쪽 변을 회전시키는 과정에서 (x , y)에는 (x + 1 , y)의 값이 덮어쓰기가 될 것이다. 즉 ! (x , y)의 값이 K로 남아있질 않을 것이다.

이 상태에서, 왼쪽변, 아랫변, 오른쪽변, 그리고 마지막으로 윗쪽변을 회전시키게 되면, (x + 1 , y)의 값으로 덮어쓰기가 된 (x , y)의 값이 빨강점이 있는 좌표에 저장이 될 것이다.

그렇기 때문에 ! 모든 회전을 시작하기 전에, (x , y)의 값을 따로 저장을 해주어야 한다.

이 따로 저장한 값을 이용해서 가장 마지막에 빨강색 점의 좌표를 다시 설정해 주어야 한다.

 

이 전체 과정을 코드로 나타내면 다음과 같다.

	int Temp = MAP[x][y];
    
	for (int i = x; i < xx; i++)
	{
		MAP[i][y] = MAP[i + 1][y];
	}
    
	for (int i = y; i < yy; i++)
	{
		MAP[xx][i] = MAP[xx][i + 1];
	}
    
	for (int i = xx; i > x; i--)
	{
		MAP[i][yy] = MAP[i - 1][yy];
	}
    
	for (int i = yy; i > y; i--)
	{
		MAP[x][i] = MAP[x][i - 1];
	}
	MAP[x][y + 1] = Temp;

 

#2. 최솟값 구하기

이 과정에서 최솟값을 구하는 것은 너무나도 간단하다.

회전을 할 때, 회전 시키는 모든 값들을 비교해서 최소값을 찾기만 하면 되기 때문이다.

즉, 위의 코드에서 다음과 같은 부분만 추가를 해주면 최솟값을 구할 수 있다.

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;

 

[ 소스코드 ]

#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++)
    {
        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;
}