삼각 달팽이

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

 

반시계방향으로 달팽이 채우기를 진행해야 한다.

 

2차원배열을 이용했는데, 1열에 1칸, 2열에 2칸, n열에 n칸으로 계산을 하면 복잡할거 같아서, n * n 의 배열을 염두에 뒀다.

 

class Solution {
	// 진행 방향
    // 벽(?)에 부딫힐때마다 방향을 전환하며, 총 3가지 방향으로 진행된다.
    int[] dx = {1, 0, -1};
    int[] dy = {0, 1, -1};
    
    public int[] solution(int n) {
        
        // 방문 여부 체크
        boolean[][] checked = new boolean[n+1][n+1];
        // 숫자 기록용
        int[][] boxes = new int[n+1][n+1];
        
        // 박스에 넣을 숫자
        int num = 1;
        
        // 1, 1은 일단 숫자 넣어놓고 시작
        boxes[1][1] = num++;
        checked[1][1] = true;
        
        // box 좌표
        int[] pos = new int[] {1, 1};
        // 진행 방향
        int vector = 0;
        // n 값에 따른 숫자 젤 큰 값(등차수열 합)
        int last = n * (1 + n) / 2;
        
        while (num <= last) {
            
            if (vector > 2) vector -= 3;
            
            int x = pos[0] + dx[vector];
            int y = pos[1] + dy[vector];
            
            if (x > n || y > n) {
            	// x, y가 범위를 벗어났을때
                vector++;
                continue;
            } else if (x < 1 || y < 1) {
            	// x, y가 1보다 작을 때
                vector++;
                continue;
            } else if (checked[x][y]) {
            	// 이미 방문한 좌표
                vector++;
                continue;
            }
            
            pos = new int[] {x, y};
            
            checked[pos[0]][pos[1]] = true;
            boxes[pos[0]][pos[1]] = num++;
            
        }
        
        int[] answer = new int[last];
        int idx = 0;
        
        // 박스에 새겨넣은 숫자를 순서대로 꺼냄
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (checked[i][j]) {
                    answer[idx++] = boxes[i][j];
                }
            }
        }
        
        
        return answer;
    }
    
    
}