[프로그래머스][Level2] 삼각 달팽이 c++

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/68645

문제

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 1,000 이하입니다.

풀이 과정

익숙해져야 되는 대표적인 구현 문제이다.
n = 1일 때는 1, n = 2일 때는 3, n = 3일 때는 6, n = 4일때는 10이므로
정수 n은 n * (n + 1) / 2 까지 도는 것을 알 수 있다.

만약 다음 방향으로 가는 곳이 0보다 작거나 n보다 크거나 같으면
가면 안 되는 방향이기 때문에 방향을 돌려준다.
또한, 0이 아니라면 이미 방문했다는 뜻이므로 방향을 돌려준다.

반복문이 끝났으면 0이 아닌 곳을 answer 벡터에 넣어주면 된다.

#include <string>
#include <vector>

using namespace std;

int dx[3] = {0, 1, -1};
int dy[3] = {1, 0, -1};
int arr[1001][1001];

int x, y, dir;

vector<int> solution(int n) {
    vector<int> answer;
    for(int i = 1; i <= n * (n + 1) / 2; i++){
        arr[y][x] = i;

        if(y + dy[dir] < 0 || y + dy[dir] >= n || x + dx[dir] < 0 || x + dx[dir] >= n || arr[y + dy[dir]][x + dx[dir]] != 0){
            dir = (dir + 1) % 3;
        }
        y += dy[dir];
        x += dx[dir];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(arr[i][j]) answer.push_back(arr[i][j]);
        }
    }
    return answer;
}