행렬 테두리 회전하기

---

🔗 🔗 행렬 테두리 회전하기

문제 설명

---

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

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

제한 사항

---

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

입출력 예

---

입출력 예 설명

---

입출력 예 #1

회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

입출력 예 #2

회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

입출력 예 #3

이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.

풀이

---

행렬의 테두리 회전 알고리즘을 잘 짜야한다.

사각형으로 회전하므로, 각 변마다 회전하는 알고리즘을 for문으로 구성해야한다. 다행히 회전 방향은 시계 방향으로 정해져있다.

데이터를 정상적으로 회전시키려면, 회전하는 방향과 반대 방향으로 진행해야 데이터를 온전히 보존하면서 회전할 수 있다.

좌 -> 하 -> 우 -> 상 순으로 진행하며 데이터를 회전시킨다. 방법은 아래와 같다.

• minPos: $(x_{min}, y_{min})$
• maxPos: $(x_{max}, y_{max})$

1. 좌측 회전

좌측 회전을 수행한다.

JAVA
1
2
3
4
for (int j = minPos[0]; j < maxPos[0]; j++)
{
	board[j][minPos[1]] = board[j + 1][minPos[1]];
}

(2, 2), (3, 2), (4, 2) 순으로 진행한다.

y좌표는 $y_{min}$으로 동일하고, x좌표만 바뀐다.

진행하며 그림을 기준으로 자신의 하단값을 자신에게 할당한다.

가장 최소 좌표인 (2, 2)의 값 8은 별도로 저장한다.

2. 하단 회전

하단 회전을 수행한다.

JAVA
1
2
3
4
for (int j = minPos[1]; j < maxPos[1]; j++)
{
	board[maxPos[0]][j] = board[maxPos[0]][j + 1];
}

(5, 2), (5, 3) 순으로 진행한다.

x좌표는 $x_{max}$로 동일하고, y좌표만 바뀐다.

진행하며 그림을 기준으로 자신의 우측값을 자신에게 할당한다.

3. 우측 회전

JAVA
1
2
3
4
for (int j = maxPos[0]; j > minPos[0]; j--)
{
	board[j][maxPos[1]] = board[j - 1][maxPos[1]];
}

(5, 4), (4, 4), (3, 4) 순으로 진행한다.

y좌표는 $y_{max}$로 동일하고, x좌표만 바뀐다.

진행하며 그림을 기준으로 자신의 상단값을 자신에게 할당한다.

4. 상단 회전

JAVA
1
2
3
4
for (int j = maxPos[1]; j > minPos[1]; j--)
{
	board[minPos[0]][j] = board[minPos[0]][j - 1];
}

(2, 4), (2, 3) 순으로 진행한다.

x좌표는 $x_{min}$으로 동일하고, y좌표만 바뀐다.

진행하며 그림을 기준으로 자신의 좌측값을 자신에게 할당한다.

회전 이후 (2, 3) 데이터가 손실되는데, 이 때 좌측 회전에서 따로 저장해둔 최소 좌표값을 할당한다.

즉, $(x_{min}, y_{min})$을 별도로 저장해두고, $(x_{min}, y_{min} + 1)$에 따로 할당하면 된다.

회전 방향과 반대로 진행하며, 자신 앞의 데이터를 자신에게 할당하는 알고리즘을 구현하는 것이 관건이다.

회전 방향이 여러개일 경우, 회전 방향마다 알고리즘을 별도로 구성해야하나, 이 문제에서는 시계방향 고정이니 신경쓸 필욘 없다.

회전 과정에서 모든 요소에 접근하게 되므로, 요소마다 값을 비교하여 최소값을 별도로 저장하면 된다.

코드

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 * 멀쩡한 사각형 클래스
 *
 * @author RWB
 * @since 2021.12.28 Tue 22:51:28
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param rows: [int] 열
	 * @param columns: [int] 행
	 * @param queries: [int[][]] 회전 대상
	 *
	 * @return [int] 해답
	 */
	public int[] solution(int rows, int columns, int[][] queries)
	{
		int[] answer = new int[queries.length];
		
		int[][] board = new int[rows][columns];
		
		for (int i = 0; i < rows; i++)
		{
			for (int j = 0; j < columns; j++)
			{
				board[i][j] = i * columns + j + 1;
			}
		}
		
		for (int i = 0; i < queries.length; i++)
		{
			int[] minPos = { queries[i][0] - 1, queries[i][1] - 1 };
			int[] maxPos = { queries[i][2] - 1, queries[i][3] - 1 };
			
			int start = board[minPos[0]][minPos[1]];
			
			int min = Integer.MAX_VALUE;
			
			// 좌측 라인 회전
			for (int j = minPos[0]; j < maxPos[0]; j++)
			{
				min = Math.min(min, board[j][minPos[1]]);
				
				board[j][minPos[1]] = board[j + 1][minPos[1]];
			}
			
			// 하단 라인 회전
			for (int j = minPos[1]; j < maxPos[1]; j++)
			{
				min = Math.min(min, board[maxPos[0]][j]);
				
				board[maxPos[0]][j] = board[maxPos[0]][j + 1];
			}
			
			// 우측 라인 회전
			for (int j = maxPos[0]; j > minPos[0]; j--)
			{
				min = Math.min(min, board[j][maxPos[1]]);
				
				board[j][maxPos[1]] = board[j - 1][maxPos[1]];
			}
			
			// 윗 라인 회전
			for (int j = maxPos[1]; j > minPos[1]; j--)
			{
				min = Math.min(min, board[minPos[0]][j]);
				
				board[minPos[0]][j] = board[minPos[0]][j - 1];
			}
			
			board[minPos[0]][minPos[1] + 1] = start;
			
			answer[i] = min;
		}
		
		return answer;
	}
}