[Kotlin] Leet Code - Spiral Matrix

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

Spiral Matrix - LeetCode

유형

구현

풀이

달팽이 모양으로 행렬의 포인터를 이동시켜보는 문제였다.

 

1. 행렬에 포인터를 두고, 오른쪽, 아래, 왼쪽, 위, 오른쪽, 아래,... 의 순서로 방향을 바꿀 수 있도록 방향 배열을 설정한다.

var row = 0; var col = 0
val dRow = intArrayOf(0, 1, 0, -1)
val dCol = intArrayOf(1, 0, -1, 0)
var dir = 0

2. 방향 변경 조건 설정

현재 위치에 있는 숫자를 정답에 추가하고 우선 현재 방향대로 한 칸 이동한다. 이 때, 아래 그림과 같이 이동한 위치가 행렬의 범위를 벗어나거나 이전에 확인했던 곳이라면 이동하기 전의 위치에서 방향을 바꿔서 다시 이동한다. 

var nextRow = row + dRow[dir]
var nextCol = col + dCol[dir]
// 현재 방향대로 이동했을 때 행렬을 벗어나거나 이전에 추가했던 위치면 방향을 변경
// 101: 확인한 곳
if (nextRow !in matrix.indices || nextCol !in matrix[0].indices || matrix[nextRow][nextCol] == 101) {
    dir = (dir + 1) % 4
}
row = row + dRow[dir]
col = col + dCol[dir]

3.  2번의 과정을 반복한다. 단, 무한 루프에 빠지지 않도록 숫자를 모두 추가했으면 반복문을 빠져나온다.

answer.add(matrix[row][col])
matrix[row][col] = 101 // 해당 위치의 숫자를 추가했다는 표시
// 다 추가했으면 스탑
if (++addCount >= addLimit) {
    break
}

전체 코드

class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        // right, down, left, up
        val dRow = intArrayOf(0, 1, 0, -1)
        val dCol = intArrayOf(1, 0, -1, 0)
        var dir = 0
        var row = 0; var col = 0 // 현재 좌표
        var addCount = 0         // 추가한 숫자 개수
        val addLimit = matrix.size * matrix[0].size // 최종 추가할 개수
        val answer = mutableListOf<Int>()
        
        while (true) {
            answer.add(matrix[row][col])
            matrix[row][col] = 101 // 해당 위치의 숫자를 추가했다는 표시
            // 다 추가했으면 스탑
            if (++addCount >= addLimit) {
                break
            }
            
            var nextRow = row + dRow[dir]
            var nextCol = col + dCol[dir]
            // 현재 방향대로 이동했을 때 행렬을 벗어나거나 이전에 추가했던 위치면 방향을 변경
            if (nextRow !in matrix.indices || nextCol !in matrix[0].indices || matrix[nextRow][nextCol] == 101) {
                dir = (dir + 1) % 4
            }
            row = row + dRow[dir]
            col = col + dCol[dir]
        }
        
        return answer
    }
}