[알고리즘] Spiral Matrix

Problem

Given a matrix of m x n elements (m rows, n columns)

Return all elements of the matrix in spiral order.

 

// input
int[][] matrix = new int[][]{
    {1,2,3,4},
    {5,6,7,8},
    {9,10,11,12}
};

// output
1 2 3 4 8 12 11 10 9 5 6 7

Code

package 배열;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SpiralMatrix {
    private int[][] dirs = new int[][]{
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };
    public List<Integer> solution(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if(matrix == null || matrix.length == 0) return result;
        int rowStart = 0;
        int rowEnd = matrix.length-1;
        int colStart = 0;
        int colEnd = matrix[0].length-1;

        while (rowStart <= rowEnd && colStart <= colEnd) {
            // 동
            for (int i = colStart; i <= colEnd; i++) {
                result.add(matrix[rowStart][i]);
            }
            rowStart++;

            // 남
            for (int i = rowStart; i <= rowEnd; i++) {
                result.add(matrix[i][colEnd]);
            }
            colEnd--;

            // 서
            if (rowStart <= rowEnd) {
                for (int i = colEnd; i >= colStart; i--) {
                    result.add(matrix[rowEnd][i]);
                }
            }
            rowEnd--;

            // 북
            if (colStart <= colEnd) {
                for (int i = rowEnd; i >= rowStart; i--) {
                    result.add(matrix[i][colStart]);
                }
            }
            colStart++;
        }
        return result;
    }

    public List<Integer> solution2(int[][] matrix) {
        int dir = 0, x = 0, y = 0;
        boolean[][] visit = new boolean[matrix.length][matrix[0].length];
        List<Integer> result = new ArrayList<>();
        result.add(matrix[x][y]);
        visit[x][y] = true;

        while (true) {
            x += dirs[dir][0];
            y += dirs[dir][1];

            if (x>=0 && y < matrix[0].length && y>=0 && x < matrix.length && !visit[x][y]) {
                result.add(matrix[x][y]);
                visit[x][y] = true;
                if(result.size() == matrix.length*matrix[0].length) break;
            } else {
                x -= dirs[dir][0];
                y -= dirs[dir][1];
                dir++;
                if(dir == 4) dir = 0;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
            {1,2,3,4,},
            {5,6,7,8},
            {9,10,11,12}
        };
        SpiralMatrix problem = new SpiralMatrix();
//        System.out.println(problem.solution(matrix).toString());
        System.out.println(problem.solution2(matrix).toString());
    }
}