LeetCode : 59. Spiral Matrix II

C언어를 처음 배울 때 익혔던? 달팽이 알고리즘이다.ㅎㅎ

오랜만에 풀어봐서 좋았닼ㅋㅋ

근데 이 풀이 방법이 사실 for문을 4번써서 간단하게 해결하는 방법도 있지만...

편한대로 풀었다.

 

방문배열을 통해 이미 방문한 좌표인지를 확인했고 범위를 벗어나거나 이미 방문한 좌표일 경우에는 방향을 바꾸도록 했다.

그래서 오, 아래, 왼, 위, 오, 아래...이런식으로 4방향이 계속적으로 반복되는 형식으로 달팽이 알고리즘이 진행된다.

 

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int map[21][21] = {0, };
        int x = 0, y = 0, num = 0;
        int visited[21][21] = {0, };
        int idx = 0; // 방향 설정
        vector<vector<int>> ans;
        
        while(num<n*n){
            num++;
            map[x][y] = num;
            visited[x][y] = 1;
            int nx = x+dx[idx];
            int ny = y+dy[idx];
            if(0>nx || nx>=n || 0>ny || ny>=n || visited[nx][ny]){
                idx = (idx+1)%4;
                nx = x+dx[idx];
                ny = y+dy[idx];
            }
            x = nx;
            y = ny;
        }
        
        for(int i=0; i<n; i++){
            vector<int> temp;
            for(int j=0; j<n; j++){
                temp.push_back(map[i][j]);
            }
            ans.push_back(temp);
        }
        
        return ans;
    }
};