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

https://school.programmers.co.kr/learn/courses/30/lessons/77485?language=cpp 

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;

    int arr[101][101];
    int side[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= columns; j++)
            arr[i][j] = ((i - 1) * columns) + j;

    for (int i = 0; i < queries.size(); i++)
    {
        int dir = 0;
        int minNum = 10010;
        int y = queries[i][0];
        int x = queries[i][1];
        int firstNum = arr[y][x];

        while (y != queries[i][0] || x != queries[i][1] + 1)
        {
            if(y==queries[i][2]&&x==queries[i][1])
                dir++;
            else if(y==queries[i][2]&&x==queries[i][3])
                dir++;
            else if(y==queries[i][0]&&x==queries[i][3])
                dir++;
            
            arr[y][x] = arr[y + side[dir][0]][x + side[dir][1]];
            y += side[dir][0];
            x += side[dir][1];
            minNum = min(minNum, arr[y][x]);
        }
        arr[y][x] = firstNum;
        minNum = min(minNum, arr[y][x]);
        answer.push_back(minNum);
    }

    return answer;
}

 

풀이 방식

그냥 테두리를 따라 밀어 옮기게 구현하면 되는 문제이다.

나는 반대로 밀어 넣어 풀었다. 예를 들어 순서를 보이겠다.

이렇게 일단 시작 지점에 올 번호를 옮겨주는 것이다. 다음 순서는 아래와 같다.

또 다음 순서를 보이겠다.

이런식으로 옮겨 넣는 것이다.

또 다음 과정을 보이겠다.

 

이런 식으로 쭉 반복을 하면 된다.

그런데 마지막에 주의할 점이 있다. 반복하다 아래의 그럼처럼

 

시작점의 원소를 옮기면 안 된다. 왜냐하면 14는 옮겨져 적절한 위치에 있는 원소이기 때문이다.

즉, 회전시킬 때 시작점의 붙어있는 오른쪽에서는 밀어 넣기를 그만하고 원래 처음 시작점의 원소를 적어줘야 한다.

 

여기서 포인트는 벽에 부딪힐 때마다 밀어 넣기의 방향이 바뀐다는 것이다.

즉, 아래의 포인트가 방향을 바꾸는 포인트가 되는 것이다.

이 포인트는 주어진 쿼리로 바로 구할 수 있다.

그리고 이런 밀어 넣기의 과정마다 최소 값을 찾아 갱신해주면 된다. 밀어 넣기가 끝나면 answer에 넣기.

 

그럼 이제 구현한 코드를 보이겠다.

int arr[101][101];
int side[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= columns; j++)
            arr[i][j] = ((i - 1) * columns) + j;

arr은 1~n까지 번호가 적인 배열을 만들 것이다.

side는 이동 방향을 표시한다.

side의 0번째는 아래로 이동하는 것이다.

side[0][0]은 y의 이동 side[0][1]은 x의 이동방향으로

현재 위치에서 각각 side[i][0 또는 1]을 더해 이동을 구현한다.

 

side는 순서대로 하, 우, 상, 좌 방향으로 이동하게 만들어져 있다.

위에서 소개한 밀어 넣기 방식으로 이동 방향은 정해져 있기에 이 순서대로 side를 만들었다.

 

int dir = 0;
int minNum = 10010;
int y = queries[i][0];
int x = queries[i][1];
int firstNum = arr[y][x];

dir은 현재 이동 방향이다 0이므로 side의 0번째로 현재 좌표를 더하면 아래로 이동한다.

dir이 1이라면 side의 1번째 -> side[1]을 이용하므로 우로 이동한다.

minNum은 테두리를 회전할 때 최솟값을 찾기 위해 갱신될 변수이다.

x, y는 시작점, firstNum은 시작점의 숫자이다.

 

while (y != queries[i][0] || x != queries[i][1] + 1)
{
	...
}

while문은 시작점의 오른쪽에 도착하면 끝나게 만들었다.

그전까지 밀어 넣기를 한다.

 

if(y==queries[i][2]&&x==queries[i][1])
	dir++;
else if(y==queries[i][2]&&x==queries[i][3])
	dir++;
else if(y==queries[i][0]&&x==queries[i][3])
	dir++;

이것은 방향이 바뀌는 포인트를 구현한 것이다.

이때 방향을 바꾸게 dir을 +1 해준다.

 

arr[y][x] = arr[y + side[dir][0]][x + side[dir][1]];
y += side[dir][0];
x += side[dir][1];
minNum = min(minNum, arr[y][x]);

이동할 방향 dir을 이용해 숫자를 이동시킨다.

그리고 현재 위치 x, y를 갱신.

이때 minNum을 찾는 과정 또한 잊지 않고 해 준다.

 

arr[y][x] = firstNum;
minNum = min(minNum, arr[y][x]);
answer.push_back(minNum);

while문을 빠져나온 뒤

현재 위치는 시작점의 바로 오른쪽에 붙어있는 위치일 것이다.

이때 처음 시작 위치의 숫자를 넣어준다.