1. 기본 개념
- grid : 회전해야 할 격자를 나타내는 2차원 배열
- L : 격자를 나누는 단위의 레벨로, 2^L * 2^L 크기의 부분 격자로 나누어 회전한다.
- size : 전체 격자의 크기 (size = 2^L)
- 격자는 여러 개의 작은 격자로 나뉘며, 각각의 작은 격자를 독립적으로 시계 방향으로 90도 회전
2. 변수 설명
- subgridSize = 2 ** L
: 회전시킬 부분 격자의 크기를 결정
예를 들어, L = 2이면 subgridSize = 2^2 = 4이 되어, 4×4 크기의 격자가 각각 회전합니다.
- newGrid : 회전 결과를 저장할 새로운 배열
- r,c : 각각 부분 격자의 시작 행과 열.
전체 격자를 부분 격자로 나누어 각각 회전해야 하기 때문에, r과 c는 subgridSize 단위로 증가
3. 내부 중첩 루프 분석
for (let r = 0; r < size; r += subgridSize) {
for (let c = 0; c < size; c += subgridSize) {
for (let i = 0; i < subgridSize; i++) {
for (let j = 0; j < subgridSize; j++) {
newGrid[r + j][c + subgridSize - i - 1] = grid[r + i][c + j];
}
}
}
}
- r,c 루프 : 격자를 subgridSize × subgridSize 부분 격자로 나누고, 각각을 처리
ex) 격자가 8×8이고 subgridSize = 4이면, r과 c는 (0, 0), (0, 4), (4, 0), (4, 4) 순으로 반복
- i, j 루프 : 각 부분 격자의 요소를 90도 회전시키는 작업
원래 격자
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
시계 방향 90도 회전 후 격자
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
4. 회전 공식
newGrid[r+j][c + subgridSize -i -1] = grid[r+i][c+j]
- r + j: 새 격자에서 새롭게 값이 들어갈 행을 나타냅니다.
원래의 열 인덱스(j)가 새 격자에서 행 인덱스가 됩니다.
즉, 90도 회전했기 때문에 원래의 열이 새로운 행이 되는 것입니다.
- c + subgridSize - i - 1: 새 격자에서 새롭게 값이 들어갈 열을 나타냅니다.
이 부분이 가장 헷갈릴 수 있는데, 이것은 90도 회전의 결과로 원래의 행 인덱스(i)가 새 격자에서 뒤집힌 열 인덱스가 되기 때문입니다.
- subgridSize - i - 1: 회전 후 원래의 행이 새 격자에서 반대쪽으로 이동하기 때문에,
열의 위치는 subgridSize에서 i를 뺀 값으로 계산됩니다.
'알고리즘 문제 풀기' 카테고리의 다른 글
백준 10159 : 저울 - javascript(dfs) (0) | 2024.10.12 |
---|---|
백준 20058 : 마법사 상어와 파이어스톰 - javascript(dfs) (0) | 2024.10.10 |
백준 13904 : 과제 - javascript(그리디) (0) | 2024.10.10 |
백준 16928: 뱀과 사다리 게임 - javascript(bfs) (0) | 2024.10.07 |
백준 1405 : 미친 로봇 - javascript(dfs) (0) | 2024.10.05 |