배열을 이용해서 풀 것이고, 예시에 나와있는 것들을 배열로 표현한다면 아래와 같이 숫자가 배치될 것이다. ( 나머지는 -1로 채울것)
번호를 채우는 방향을 하 -> 우 -> 상이므로, dx, dy로 방향 벡터를 넣어주었다.
여기에서 상 방향은 bfs를 할 때와 다르게, x좌표도 -1이 되어야 한다. (대각선 방향으로 채우므로)
숫자를 채울 n*n 배열 arr을 선언하고, 모든 칸을 0으로 초기화한다.
채워질 수 없는 칸들을 -1로 채워준다.
현재 x, y좌표와 현재 방향을 뜻하는 i, 방향을 변경할 횟수인 ii, 채워야하는 숫자 cnt를 초기화해준다.
첫 칸인 arr[0][0]은 항상 1이므로 초기 설정을 해준다.
while 문을 돌면서
현재 방향을 바꾼 횟수인 ii가 2 이상이 되면 더 이상 방향을 바꿀 수 없고, 갈 곳이 없으므로 모든 칸을 다 채웠단 의미이므로 무한루프 종료
현재 방향에 맞게 다음 좌표를 xx, yy라고 할 때, 해당 칸이 배열의 범위 안이면서, 아직 숫자가 채워지지 않았으며 -1이 아니면
해당 칸에 1 증가한 cnt를 넣어주고
현재 x, y 를 xx, yy로 변경한다.
방향 바꾼 횟수 ii를 0으로 다시 설정한다.
만약 그렇지 않으면 방향을 바꿔야 하므로 i를 1증가시키고 3으로 나눈 나머지로 바꿔주고, ii를 1 증가시킨다.
arr으로 결과배열을 리턴해야하므로, 해당 칸이 -1이 아니면 answer 배열에 push 해준다.
answer를 리턴한다.
function solution(n) {
const dx = [1, 0, -1]; // 하 우 상
const dy = [0, 1, -1]; // 하 우 상
const arr = Array.from(Array(n), () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
arr[i][j] = -1;
}
}
let x = 0; // 현재 x좌표
let y = 0; // 현재 y좌표
let i = 0; // 현재 방향 => 0:하 / 1:우 / 2:상
let ii = 0; // 방향을 변경한 횟수 => 2회를 변경했는데 더 이상 숫자를 붙일 수 없으면 종료
let cnt = 1; // 현재 채워야하는 숫자
arr[0][0] = cnt; // 첫 칸은 1로 초기값
while (true) {
if (ii > 2) break;
const xx = x + dx[i];
const yy = y + dy[i];
if (xx >= 0 && yy >= 0 && xx < n && yy < n && arr[xx][yy] == 0) {
x = xx;
y = yy;
arr[x][y] = ++cnt;
ii = 0;
} else {
i = (i + 1) % 3;
ii++;
}
}
const answer = [];
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (arr[i][j] != -1) {
answer.push(arr[i][j]);
}
}
}
return answer
}
