리트코드 - 54. Spiral Matrix

리트코드 - 54. Spiral Matrix

출처 - https://leetcode.com/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

m x n 매트리스가 주어지면 나선형 순서로 모든 요소를 반환하세요.

풀이코드

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];

        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        int direction = 0;
        int x = 0;
        int y = 0;

        for (int i = 0; i < rows * cols; i++) {
            result.add(matrix[x][y]);
            visited[x][y] = true;

            int nextX = x + dx[direction];
            int nextY = y + dy[direction];
            
            if ((0 <= nextX && nextX < rows) && (0 <= nextY && nextY < cols) && !visited[nextX][nextY]) {
                x = nextX;
                y = nextY;
                continue;
            } 
            direction = (direction + 1) % 4;
            x += dx[direction];
            y += dy[direction];
        }
        return result;
    }
}

코드설명

시계방향으로 순회하며 배열을 추가하는 문제이다.

문제를 푸는 방법은 여러가지가 있겠지만, 2차원 배열이 주어졌을 때 x값과 y값의 규칙을 찾는 것이 유사한 문제를 풀 때에도 도움이 된다.

규칙은 오른쪽 -> 아래 -> 왼쪽 -> 위 순으로 이동하므로 간단하다.

 

오른쪽으로 이동할 때 같은 행이므로 x값(여기서 x는 행의 위치)은 증가하지 않고, 아래로 이동할 때는 1 씩 증가하고, 왼쪽으로 이동할 때는 역시 증가하지 않고, 위로 이동할 때는 -1 씩 감소한다.

 

그리고 y값(열의 위치)은 순서대로 1, 0, -1, 0 이 될 것이다.

이를 배열로 만들어 저장해놓는다.

int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};

 

현재의 direction은 오른쪽이므로 0으로 설정하여 배열순회를 출발한다.

visited 배열을 만들어 방문한 배열은 true로 만들어주고, x와 y를 갱신해준다.

갱신할 때는 dx, dy 배열의 인덱스만큼 더하면 된다.

가령 오른쪽으로 이동중인 현재는 0번째 인덱스이고 y값(열의 위치)만 증가하게 된다.

1) 갱신한 x와 y가 범위 안인지

2) 방문한 배열이 아닌지

 

두 개를 확인하여 x,y값을 계속 갱신해주고, 만약 배열을 벗어난 경우 방향을 바꾸어야 한다.

direction에 +1을 해주면 방향을 바꾸는 효과를 볼 수 있고, 방향은 4가지 뿐이므로 4로 나눈 나머지를 구하면 정상적으로 갱신된다.

 

이렇게 하면 나선형으로 모든 값을 추가할 수 있다.

 

시간복잡도 - O(n*m) (n, m은 주어진 matrix의 행과 열)

공간복잡도 - O(n*m)

 

문제를 풀며 생각한 흐름과 배운 점

처음 코드

 public static List<Integer> spiralOrder(int[][] matrix) {
        int rowLen = matrix.length - 1;
        int colLen = matrix[0].length - 1;

        List<Integer> answer = new ArrayList<>();
        int rowIdx = 0;
        int colIdx = 0;

        while (rowLen > 0 && colLen > 0) {
            for (int i = colIdx; i <= colLen; i++) {
                answer.add(matrix[rowIdx][i]);
            }

            rowIdx++;

            for (int j = rowIdx; j <= rowLen; j++) {
                answer.add(matrix[j][colLen]);
            }

            colLen--;
			
            // 왼쪽으로 이동
            if (rowIdx <= rowLen) {
                for (int j = colLen; j >= colIdx; j--) {
                    answer.add(matrix[rowLen][j]);
                }
            }
            rowLen--;

            // 위로 이동
            if (colIdx <= colLen) {
                for (int j = rowLen; j >= rowIdx; j--) {
                    answer.add(matrix[j][colIdx]);
                }
            }
            colIdx++;
        }
        return answer;
    }
}

문제를 그림을 그려보니 가로 길이에서 하나씩 빠지고, 세로 길이에서 하나씩 빠지는 패턴이 나왔다.

오른쪽, 아래쪽은 문제가 없었는데, 왼쪽, 위쪽으로 이동하는 코드가 약간 복잡해서 if문을 사용해야 했다.

4방향을 이동하는 코드를 적으면서 matrix의 인덱스를 찾는게 무척이나 헷갈려 개선이 필요했다.

 

개선(방향벡터)

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int[][] dv = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];

        int nowIdx = 0;
        int r = 0;
        int c = 0;

        for (int i = 0; i < rows * cols; i++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;

            int nextR = r + dv[nowIdx][0];
            int nextC = c + dv[nowIdx][1];

            if ((0 <= nextR && nextR < rows) && (0 <= nextC && nextC < cols) && !visited[nextR][nextC]) {
                r = nextR;
                c = nextC;
            } else { // 방향 변경
                nowIdx = (nowIdx + 1) % 4;
                r += dv[nowIdx][0];
                c += dv[nowIdx][1];
            }

        }
        return result;
    }
}

그래서 이를 간단히 하기 위해 2차원 배열을 만들었는데 찾아보니 방향 벡터라는 명칭이 있었다.

코드를 구현해놓고 보니 dp배열에서 이동하는 것과 매우 유사해서 dp는 아니지만 dp형태로 푸는 것이 가독성 면에서 더 낫겠다고 판단이 들어 풀이 코드로 수정했다.

 

정리

이차원배열이 주어지면 규칙성을 찾아 이동하는 방법