[LeetCode] 54. Spiral Matrix - 구현(Implementation) JAVA

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

코드설명

구현(Implementation) 문제입니다.

 

이 문제의 경우, mxn 개의 matrix만큼의 기저사례를 설정하고 벽을 만나거나, 이전에 이미 방문한 곳이라면 방향을 바꿔주고 MOD 연산을 통해 이동처리하면 됩니다.

저의 경우 DFS를 통해 구현했는데, FOR문으로 해도 가능합니다.

코드

class Solution {
    int[][] dir = new int[][]{
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 1 && matrix[0].length == 1){
            return Arrays.asList(matrix[0][0]);
        }
        return DFS(0, 0, 0, 0, new ArrayList<Integer>(), matrix, new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, new boolean[matrix.length][matrix[0].length]);
    }   

    List<Integer> DFS(int level, int r, int c, int dirIdx, ArrayList<Integer> answer, int[][] matrix, int[][] dir, boolean[][] visited){
        if(level == matrix.length * matrix[0].length - 1){
            return answer;
        }
        if(r == 0 & c == 0) {
            answer.add(matrix[r][c]);
            visited[0][0] = true;
        }
        int nr = r + dir[dirIdx][0];
        int nc = c + dir[dirIdx][1];
        if(nr < 0 || nc < 0 || nr >= matrix.length || nc >= matrix[0].length || visited[nr][nc] == true){
            dirIdx = (dirIdx + 1) % 4;
            nr = r + dir[dirIdx][0];
            nc = c + dir[dirIdx][1];
        }

        visited[nr][nc] = true;
        answer.add(matrix[nr][nc]);
        return DFS(level + 1, nr, nc, dirIdx, answer, matrix, dir, visited);
    }
}