LeetCode/Spiral Matrix

예전의 나였다면 어떻게든 수학식으로 일반화시켜서 해당 식에서 바로 값을 추출해서 vector에 넣고 반환했을 것이다.
수학적으로 정리해서 깔끔하게 짧은 시간내에 완성하는건 좋은데 시간이 많이 걸린다.

그냥 단순무식하게 문제에서 주어진 것처럼 빙글빙글 탐색하면 된다!
1. 우->하->좌->상 으로 탐색하므로 이를 깔끔하게 처리할 방향배열 dy dx를 선언한다.

2. 현재 위치 y,x 변수, 다음 이동할 위치 nextY, nextX 변수 선언, cnt는 이동횟수, num은 전체 칸 갯수. 전체 칸 갯수만큼 이동하고 나면 루프를 빠져나와서 res를 반환하면 된다.

3. h와 w는 이동할 수 있는 곳인지 아닌지를 판단하기 위해 저장한다. dir은 dy dx벡터에서 이용할 방향의 인덱스

---

1. 0,0에서 시작하므로 먼저 res에 값을 넣는다.

2. dir방향대로 다음 이동할 곳을 탐색한다.

3. 탐색한 곳이 배열의 바깥이거나, 이미 탐색한 곳(값을 0으로 밀어둔 곳)이라면 해당 방향으로 갈 수 있는만큼 간 것이므로 방향을 꺾는다(dir = (dir+1)%4);

4. 해당 방향은 무조건 가능하다.(직관적으로 알 수 있다...) 확인하지 않고 nextY nextX를 갱신하고 현재 위치의 matrix값을 갱신한 뒤 cnt를 증가시키고 이동한다.

5. 1로 루프

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        
        int y = 0;
        int x = 0;
        int nextY;
        int nextX;
        
        int cnt = 1;
        int num = matrix.size() * matrix[0].size();
        
        int h = matrix.size();
        int w = matrix[0].size();
        
        int dir = 0;
        while(true)
        {
            //우 하 좌 상 쭉 가다가
            res.emplace_back(matrix[y][x]);
            
            //다음 이동할 곳 탐색
            nextY = y + dy[dir];
            nextX = x + dx[dir];
            
            //만약 이동이 안된다면
            if(nextY < 0 || nextY >= h)
            {
                dir = (dir+1)%4;
            }
            else if(nextX < 0 || nextX >= w)
            {
                dir = (dir+1)%4;
            }
            else if(matrix[nextY][nextX] == 0)
            {
                dir = (dir+1)%4;
            }
            
            //다시 탐색
            nextY = y + dy[dir];
            nextX = x + dx[dir];
            
            //방문표시 및 cnt 증가
            matrix[y][x] = 0;
            cnt++;
            y = nextY;
            x = nextX;
            
            //전체 원소 수 만큼 전진했으면 break;
            if(cnt > num) break;
        }
        
        return res;
    }
};