2021 Dev-Matching: 웹 백엔드 개발자(상반기)(행렬 테두리 회전하기)

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

 

예시는 다음과 같다.

쿼리가 다음과 같이 주어졌을때 각각의 쿼리마다 최소가 되는 숫자는 아래 그림을 통해 알 수 있다.

이 문제는 따로 알고리즘이 들어가지 않는다. 각각의 테두리를 순회하면서 이전 숫자를 기억하고 다음 숫자에 업데이트 해주면 된다. 처음에는 복잡하게 queue에 넣어서 어쩌구 저쩌구 하려고 했는데 뻘짓이였다.

#include<vector>
#include<queue>
#include<tuple>
#include<algorithm>
using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries)
	{
		vector<int> answer;
		int map[101][101] = { 0, };

		int start = 1;
		for(int i = 0; i < rows; i++)
		{
			for(int j = 0; j < columns; j++)
			{
				map[i][j] = start;
				start++;
			}
		}

		for(auto query :queries)
		{
			int minNum = 99999999;
			int sx, sy, ex, ey;
			for(int j = 0; j < query.size(); j++)
			{
				if(j == 0)
				{
					sx = query[j];
				}
				if(j == 1)
				{
					sy = query[j];
				}
				if(j == 2)
				{
					ex = query[j];
				}
				if(j == 3)
				{
					ey = query[j];
				}
			}

			int nx = sx-1;
			int ny = sy-1;
			int before;
			int next = map[sx-1][sy-1];
			while(true)
			{
				before = next;
				if(nx == sx-1 && ny < ey-1)
				{
					ny++;
				}
				else if(nx < ex-1 && ny == ey-1)
				{
					nx++;
				}
				else if(nx == ex-1 && ny > sy-1)
				{
					ny--;
				}
				else if(nx > sx-1 && ny == sy-1)
				{
					nx--;
				}

				next = map[nx][ny];
				map[nx][ny] = before;

				minNum = min(minNum, before);

				if(nx == sx-1 && ny == sy-1)
				{
					break;
				}
			}

			answer.push_back(minNum);		
		}
		return answer;
	}