[Grind75-LeetCode] Spiral Matrix JAVA

반응형

728x90

[Grind75-LeetCode] Spiral Matrix - Medium

---

접근

• 구현

---

풀이

2차원 배열의 원소들을 나선형으로 접근할 때 원소 접근 순서를 List에 담아 반환하는 문제이다. 내용 자체는 정말 간단한 문제이기 때문에 예제 그림 한 번만 보면 바로 이해할 수 있는 문제이다. 내용 또한 크게 어려울 것 없기 때문에 쉽게 풀 수 있다.

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

        int length = matrix.length * matrix[0].length;
        int xMax = matrix.length - 1;
        int yMax = matrix[0].length - 1;
        int x = 0;
        int y = 0;

        boolean[][] isVisited = new boolean[xMax + 1][yMax + 1];
        int flag = 0;

변수와 이것저것 사용하는 게 좀 많다. 우선 리스트에 담아야 할 총개수를 length 변수로 뽑았다. 그리고 배열의 마지막 인덱스를 각각 뽑았고 인덱스로 사용될 x, y 변수도 선언했다. 방문체크를 위한 배열을 하나 사용하고 flag 변수를 통해 이동할 방향을 지정해 주었다.

	while (result.size() < length) {
            result.add(matrix[x][y]);
            isVisited[x][y] = true;

            switch (flag) {
                case 0:	//정방향
                    if (y == yMax || isVisited[x][y+1]) {
                        flag = 1;
                        x++;
                    } else {
                        y++;
                    }
                    break;
                case 1:	//아래
                    if (x == xMax || isVisited[x+1][y]) {
                        flag = 2;
                        y--;
                    } else {
                        x++;
                    }
                    break;
                case 2:	//역방향
                    if (y == 0 || isVisited[x][y-1]) {
                        flag = 3;
                        x--;
                    } else {
                        y--;
                    }
                    break;
                case 3:	//위
                    if (x == 0 || isVisited[x-1][y]) {
                        flag = 0;
                        y++;
                    } else {
                        x--;
                    }
                    break;
            }
        }
        return result;
    }

코드는 긴데 내용은 별거 없다. flag 변수의 값을 통해 현재 진행 방향이 어디인지 체크한다. flag가 0인 경우 정방향으로 왼쪽에서 오른쪽으로 이동하게 된다. 이동마다 y 값이 증가하게 되고 y 값이 배열 끝에 도달했거나 이미 방문했던 곳이라면 flag를 1로 변경한다.  flag 1은 위에서 아래로 이동하게 된다. 이동마다 x의 값이 증가하게 되고 x 값이 끝에 도달했거나 방문했던 곳이라면 flag를 2로 변경한다. flag 2는 오른쪽에서 왼쪽으로 역방향 이동을 하게 된다. 이동마다 y 값이 감소하고 y의 값이 0으로 배열 끝에 도달하거나 방문했던 곳이라면 flag를 3으로 변경한다. flag 3은 마지막 아래에서 위로의 이동으로 이동마다 x 값이 감소하고 x 값이 0이 되거나 방문했던 곳이라면 다시 flag를 0으로 변경한다. 먼저 방문을 한 뒤 x, y 좌표의 값을 올리는 형태이기 때문에 다음 위치의 방문 여부를 검사해야 하고 flag가 바뀌는 시점 이미 해당 좌표의 값은 추가가 되어 있는 상태이기 때문에 flag 변경과 같이 다음 이동 방향으로 좌표 값을 올려주어야 중복을 피할 수 있다.

flag

 

각 flag의 이동 방향을 그림으로 나타낸 것이다. 

---

전체 코드

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

        int length = matrix.length * matrix[0].length;
        int xMax = matrix.length - 1;
        int yMax = matrix[0].length - 1;
        int x = 0;
        int y = 0;

        boolean[][] isVisited = new boolean[xMax + 1][yMax + 1];
        int flag = 0;

        while (result.size() < length) {
            result.add(matrix[x][y]);
            isVisited[x][y] = true;

            switch (flag) {
                case 0: //정방향
                    if (y == yMax || isVisited[x][y+1]) {
                        flag = 1;
                        x++;
                    } else {
                        y++;
                    }
                    break;
                case 1: //아래
                    if (x == xMax || isVisited[x+1][y]) {
                        flag = 2;
                        y--;
                    } else {
                        x++;
                    }
                    break;
                case 2: //역방향
                    if (y == 0 || isVisited[x][y-1]) {
                        flag = 3;
                        x--;
                    } else {
                        y--;
                    }
                    break;
                case 3: //위
                    if (x == 0 || isVisited[x-1][y]) {
                        flag = 0;
                        y++;
                    } else {
                        x--;
                    }
                    break;
            }
        }
        return result;
    }
}