(Matrix, Medium) Spiral Matrix

https://leetcode.com/problems/spiral-matrix/description/

우, 하, 좌, 상 방향으로 매트릭스를 순회하는 문제다.
내가 생각하는 핵심 코드는 아래와 같이 구성되어야 함

• 방향 배열 정하기 (우, 하, 좌, 상) + 방향 배열 인덱스
• visited 배열로 이미 방문한 지점 체크
• x와 y값을 기준 방향 배열에 따라 증감하면서 다음 요소 순회

y,x 만났을 때 리스트에 넣고 visited 체크해준다.
그리고 현재 방향 값을 더해서 next x, next y 값을 구해주는데

이후 next x, next y가 닿을 수 없는 지점이라면 방향을 돌려서 다시 계산하여 갱신한다.

참고로 모든 요소 순회는 언젠가 끝나니까 while의 종료 시점은 count == total로 봤다.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        List<Integer> result = new ArrayList<>();

        int m = matrix.length;
        int n = matrix[0].length;

        // 우, 하, 좌, 상
        int[][] directions = new int[][] {
            { 0, 1 },
            { 1, 0 },
            { 0, -1 },
            { -1, 0 }
        };
        int dir = 0;

        boolean[][] visited = new boolean[m][n];

        int x = 0;
        int y = 0;

        int count = 0;
        int total = m * n;

        while (count < total) {
            result.add(matrix[y][x]);
            visited[y][x] = true;

            int nx = x + directions[dir][1];
            int ny = y + directions[dir][0];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[ny][nx]) {
                dir = (dir + 1) % directions.length;
                nx = x + directions[dir][1];
                ny = y + directions[dir][0];
            }

            x = nx;
            y = ny;

            count++;
        }

        return result;
    }
}

궁금해서 GPT한테 개선해보라 시켰다.
시간복잡도는 O(N)이상 줄일 수는 없어 보이고, 공간복잡도를 줄이는 방법을 제시해줬다.

top, left, right, bottom 변수를 두고 바운더리를 하나씩 축소해가는 방법이라고 한다.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        List<Integer> result = new ArrayList<>();

        int m = matrix.length;
        int n = matrix[0].length;

        int top = 0;
        int bottom = m - 1;
        int left = 0;
        int right = n - 1;

        while (top <= bottom && left <= right) {

            // 1. 우
            for (int col = left; col <= right; col++) {
                result.add(matrix[top][col]);
            }
            top++;

            // 2. 하
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--;

            // 3. 좌
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    result.add(matrix[bottom][col]);
                }
                bottom--;
            }

            // 4. 상
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++;
            }
        }

        return result;
    }
}