leetcode 54, Spiral Matrix

문제 설명

mxn 배열이 주어졌을 때 나선형 방향의 숫자 배열을 구하는 문제이다.

https://leetcode.com/problems/spiral-matrix/submissions/1059603293/

LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이

문제에는 3x3만 주어져 있지만, 직접 4x4를 그려 보면 어떤 방식으로 배열을 만들어야 할지 대충 감이 올 것이다.

 

문제를 딱 봐도 알겠지만, 직접 좌표의 방향 배열을 만들어 줘야 한다. 나는 나선형이 움직이는 방향대로 오른쪽, 아래, 왼쪽, 위쪽 이렇게 네 방향으로 배열을 만들어 줬다.

public static int[] dR = {0, 1, 0, -1};
public static int[] dC = {1, 0, -1, 0};

 

그리고 while문을 돌려주는데, 조건은 해당 좌표의 숫자가 맨 마지막이 아니다는 것이다. 해당 좌표의 숫자가 맨 마지막임을 아는 방법은 해당 좌표를 기준으로 상, 하, 좌, 우를 확인해서 모두 방문했다면 맨 마지막이고 아니면 계속해서 나아가야 한다는 것이다.

    public boolean findFinish(int r, int c) {
        boolean flag = false;

        if (findInMap(r-1, c)) {
            if (!visit[r-1][c]) {
                return false;
            }
        }
        
        if (findInMap(r+1, c)) {
            if (!visit[r+1][c]) {
                return false;
            }
        }

        if (findInMap(r, c+1)) {
            if (!visit[r][c+1]) {
                return false;
            }
        }

        if (findInMap(r, c-1)) {
            if (!visit[r][c-1]) {
                return false;
            }
        }

        return true;
    }

참고로 findInMap은 좌표가 map 안에 있는지 아닌지를 확인하는 메소드이다.

public boolean findInMap(int r, int c) {
        if (r >= 0 && r < m && c >= 0 && c < n) {
            return true;
        }
        return false;
}

맨 마지막 숫자가 아니라면 해당 좌표를 true로 만들어 준다. 그리고 answer에 넣어준다. 후에 주어진 방향으로 새로운 좌표를 만들어 준다. 그런데, 이때 해당 방향으로 계속 나가지 못하는 경우가 두 가지 있다.

 

하나는 범위를 벗어난 것이고 다른 하나는 이미 해당 좌표를 방문한 경우이다. 만일 이 경우에는 방향을 바꿔줘야 하므로 index에다가 (index+1)%4를 넣어준다. 이때, 우리는 나선형이 움직이는 방향으로 좌표 배열을 만들어줬다는 걸 기억하고 해당 좌표 배열 안에서만 돌아가야 하니 %4를 해주는 것이다.

 

참고로 범위를 벗어난 경우는 첫 번째 나선형에서 보여지며 이미 좌표를 방문한 경우는 두 번째 이후의 나선형에서 보여지는 현상이다.

 

그리고 새로 만든 방향으로 가는 새 좌표를 다시 계산해준 후 현재 좌표를 새 좌표로 갱신한다.

        while(!findFinish(r, c)) {
            visit[r][c] = true;
            //System.out.print(matrix[r][c]);
            answer.add(matrix[r][c]);
            int nR = r + dR[index];
            int nC = c + dC[index];

            if (!findInMap(nR, nC) || visit[nR][nC]) {
                index = (index+1)%4;
                nR = r + dR[index];
                nC = c + dC[index];
            }

            r = nR;
            c = nC;
        }

그리고 맨 마지막 좌표일 경우 반복문을 탈출하게 하였으니 answer에다가 맨 마지막 좌표를 넣어주면 된다.

answer.add(matrix[r][c]);

코드

java

class Solution {

    public static int n;
    public static int m;
    public static int[] dR = {0, 1, 0, -1};
    public static int[] dC = {1, 0, -1, 0};
    public static boolean[][] visit;

    public List<Integer> spiralOrder(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        int r = 0;
        int c = 0;
        int index = 0;
        visit = new boolean[m][n];
        List<Integer> answer = new ArrayList<>();

        while(!findFinish(r, c)) {
            visit[r][c] = true;
            //System.out.print(matrix[r][c]);
            answer.add(matrix[r][c]);
            int nR = r + dR[index];
            int nC = c + dC[index];

            if (!findInMap(nR, nC) || visit[nR][nC]) {
                index = (index+1)%4;
                nR = r + dR[index];
                nC = c + dC[index];
            }

            r = nR;
            c = nC;
        }

        answer.add(matrix[r][c]);

        return answer;
    }

    public boolean findFinish(int r, int c) {
        boolean flag = false;

        if (findInMap(r-1, c)) {
            if (!visit[r-1][c]) {
                return false;
            }
        }
        
        if (findInMap(r+1, c)) {
            if (!visit[r+1][c]) {
                return false;
            }
        }

        if (findInMap(r, c+1)) {
            if (!visit[r][c+1]) {
                return false;
            }
        }

        if (findInMap(r, c-1)) {
            if (!visit[r][c-1]) {
                return false;
            }
        }

        return true;
    }

    public boolean findInMap(int r, int c) {
        if (r >= 0 && r < m && c >= 0 && c < n) {
            return true;
        }
        return false;
    }
}