[LeetCode] 54. Spiral Matrix

여전히 쓸데없는 실수가 잦다.

 

재귀를 이용했고, 방문 지점을 음수로 덮어서 처리하려그랬는데,

matrix에 값이 -100~100 까지인지를 안보고 했다가 Submit 한번을 날렸다.

 

그 외에도 놓친 부분이 많았다.

재귀를 써도 되고, 메모리를 줄이고 싶다면 for loop도 충분히 가능한 문제로 보인다.

 

class Solution {
    vector<int> result;

    int direction[4][2] = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };
    
    int cur_direction = 0;
public:
    
    void dfs ( int y, int x, vector<vector<int>>& matrix )
    {
        
        result.push_back(matrix[y][x]);        
        matrix[y][x] = -999;        
        
        int next_y = direction[cur_direction][0] + y;
        int next_x = direction[cur_direction][1] + x;

        if ( next_y < matrix.size() && next_x < matrix[0].size()
            && next_y >= 0 && next_x >= 0 && matrix[next_y][next_x] != -999 )
        {
            dfs( next_y, next_x, matrix );
        }
        else 
        {
            cur_direction = (cur_direction+1)%4;
            
            next_y = direction[cur_direction][0] + y;
            next_x = direction[cur_direction][1] + x;
            
            if ( next_y < matrix.size() && next_x < matrix[0].size()
                && next_y >= 0 && next_x >= 0 && matrix[next_y][next_x] != -999 )
            {
                dfs( next_y, next_x, matrix );
            }
        }
        
    }
    
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
        dfs( 0, 0, matrix );        
        return result;
    }
};