54. spiral matrix (medium)

BFS를 풀때 사방탐색을 했던 경험이 있다면 쉽게 풀 수 있는 문제.

너무 오랜만에 풀어서 dx, dy 방향이 헷갈렸다.. ;;

 

세로가 M, 가로가 N

	(1)ㅡㅡㅡ	ㅡㅡ>
(4) ㅜ ㅣ ㅣ			(2) ㅣ ㅣ ㅣ
ㅣ ㅣ ㅣ	(3)<ㅡㅡ	ㅡㅡㅡ	ㅣ ㅣ ㅗ

 

1. 우측으로 이동시 : y가 ++

2. 아래로 이동시 : x가 ++

3. 좌측으로 이동시 : y가 --

4. 위쪽으로 이동시 : x가 --

 

N = 3, M = 4

dx = {0, 1, 0, -1}

dy = {1, 0, -1, 0}

 

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

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int N = matrix.length, M = matrix[0].length;
        visit = new boolean[N][M];

        int d = 0, nx = 0, ny = 0;
        visit[0][0] = true;
        ans.add(matrix[0][0]);

        while (true) {
            if (ans.size() == N * M) {
                return ans;
            }
            nx += dx[d];
            ny += dy[d];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M || visit[nx][ny]) {
				// 만약 경계에 닿았다면, 방향을 바꿔야 하기 때문에, 이전 칸으로 다시 되돌린다.
				nx -= dx[d];
                ny -= dy[d];
                d++;
                d %= 4;
                continue;
            }

            visit[nx][ny] = true;
            ans.add(matrix[nx][ny]);
        }
    }