나선형으로 배열을 채우는 방식은 어떻게 구현해야 할까?
→ 배열의 시작 위치에서 시계방향으로 이동하며 숫자를 채워나가는 방식을 구현해야한다.
→ 경계(배열의 끝 점)와 이미 방문한 위치를 잘 처리해주는 것이 중요
주어진 값은 n * n 크기의 2차원 배열이므로 element는 1부터 n^2까지 채워야 한다.
• 오른쪽: dx = 0, dy = 1
• 아래쪽: dx = 1, dy = 0
• 왼쪽: dx = 0, dy = -1
• 위쪽: dx = -1, dy = 0
//n*n 크기의 2차원 배열 생성
int[][] spiral = new int[n][n];
int[] dx = {0, 1, 0, -1}; //행
int[] dy = {1, 0, -1, 0}; //열
int x=0, y=0;
int direction=0; //이동방향 : 0 = 오른쪽
//1. 현재 위치에 1 채우기
spiral[x][y] = i; //i는 현재 채울 수
//2. 다음위치 계산
//오른쪽으로 이동할 때는 y가 1씩 증가하므로 nx = x + dx[direction], ny = y + dy[direction]
int nx = x + dx[direction]; //다음 행
int ny = y + dy[direction]; //다음 열
//3. 경계 확인
if(nx < 0 || nx >= n || ny < 0 || ny >= n || spiral[nx][ny] != 0){
direction = (direction + 1) % 4; //방향 시계방향으로 전환
ny = y + dy[direction]; //새로운 방향으로 이동
}
//4. 새로운 위치로 이동
//계산된 다음 위치로 이동하여 숫자채우기 반복
x = nx;
y = ny;
direction = (direction + 1) % 4
이 코드에서의 direction 값은 다음과 같은 네 가지 이동 방향을 표현한다.
0: 오른쪽으로 이동
1: 아래로 이동
2: 왼쪽으로 이동
3: 위로 이동
즉, 0 → 1 → 2 → 3의 순서로 오른쪽 → 아래 → 왼쪽 → 위로 이동
이 네 가지 방향을 계속해서 반복
• nx < 0 || nx >= n: 행(nx)이 배열의 경계를 벗어나는지 확인합니다.
• nx < 0: 배열의 위쪽 경계를 벗어남.
• nx >= n: 배열의 아래쪽 경계를 벗어남.
• ny < 0 || ny >= n: 열(ny)이 배열의 경계를 벗어나는지 확인합니다.
• ny < 0: 배열의 왼쪽 경계를 벗어남.
• ny >= n: 배열의 오른쪽 경계를 벗어남.
class Solution {
public int[][] solution(int n) {
int[][] spiral = new int[n][n];
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int x = 0, y = 0;
int direction = 0;
for (int i = 1; i <= n * n; i++) {
spiral[x][y] = i;
int nx = x + dx[direction];
int ny = y + dy[direction];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || spiral[nx][ny] != 0) {
direction = (direction + 1) % 4;
nx = x + dx[direction];
ny = y + dy[direction];
}
x = nx;
y = ny;
}
return spiral;
}
}