[프로그래머스] Lv.0 정수를 나선형으로 배치하기

Dev.Dana·2024년 10월 19일
0

Algorithm

목록 보기
6/25
post-thumbnail

나선형으로 배열을 채우는 방식은 어떻게 구현해야 할까?

→ 배열의 시작 위치에서 시계방향으로 이동하며 숫자를 채워나가는 방식을 구현해야한다.

→ 경계(배열의 끝 점)와 이미 방문한 위치를 잘 처리해주는 것이 중요

주어진 값은 n * n 크기의 2차원 배열이므로 element는 1부터 n^2까지 채워야 한다.

나선형 배열을 채우는 방법

  1. 빈 2차원 배열을 만든다.
  2. 배열의 첫번째 값부터 시작하여 오른쪽으로 이동하며 숫자를 채운다.
  3. 배열의 경계, 끝 점을 만나거나 이미 값이 채워진 곳을 만나면 방향을 바꾼다.
  4. 오른쪽, 아래, 위쪽을 반복해나가며 시계방향으로 이동한다.

방향 배열을 활용한 이동

  • 이동하는 방향은 우, 하, 상, 좌의 순서로 처리한다.
  • 방향을 바꾸는 규칙을 저장해두고, 방향 전환이 필요할 때마다 해당 값을 이용하여 방향을 전환한다.

방향 바꾸는 규칙

오른쪽: dx = 0, dy = 1

아래쪽: dx = 1, dy = 0

왼쪽: dx = 0, dy = -1

위쪽: dx = -1, dy = 0

  • 위 4가지 방향을 차례로 반복하며 경계를 만나면 방향을 변경한다.

코드로 확인하기

  1. 빈 배열 생성
//n*n 크기의 2차원 배열 생성
int[][] spiral = new int[n][n];
  1. 방향 배열 생성
int[] dx = {0, 1, 0, -1}; //행
int[] dy = {1, 0, -1, 0}; //열
  1. 초기 위치 설정
int x=0, y=0;
int direction=0; //이동방향 : 0 = 오른쪽
  • 시작위치는 (0, 0)
  • 첫번째 숫자 1을 (0, 0)에 넣고 이동은 오른쪽부터 시작하기 때문에 현재방향은 0번 인덱스부터 시작한다.
  1. 배열을 순회하며 숫자 채우기
//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;
  • 1부터 n²까지의 숫자를 차례대로 배열에 채움
  • 각 숫자를 현재 위치에 넣은 후, 다음 위치를 계산하고 이동
  • (direction + 1) % 4:
    • 현재 방향에서 다음 방향으로 전환
    • 이 연산을 통해 0 → 1 → 2 → 3 → 0으로 순환하며 방향을 바꿀 수 있다.
  • nx < 0 || nx >= n:
    • 배열의 경계를 넘는지 확인
  • spiral[nx][ny] != 0:
    • 이미 값이 채워진 곳인지 확인

나선형 방향 탐색 / 4방향 탐색 시

direction = (direction + 1) % 4

  • 이 코드는 방향을 시계방향으로 전환하기 위한 방법

이 코드에서의 direction 값은 다음과 같은 네 가지 이동 방향을 표현한다.

  1. 0: 오른쪽으로 이동

  2. 1: 아래로 이동

  3. 2: 왼쪽으로 이동

  4. 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;
    }
}
profile
어제의 나보단 나은 오늘의 내가 되기를

0개의 댓글