정수 나선형 배치

달팽이 배열

 

이건 0lv 문제인데 며칠 째 못 풀고 있다.

이전에 알았던 방법을 떠올리려 해보아도 규칙이 맞지 않다.

기역, 니은으로 끊어서 n*n-1부터 시작하여 2씩 줄어든다. 라고 기억하는데 

첫 xy = 7, 둘째 5는 맞아도, 둘째 x=3, y = 2여서 어찌 처리해야 할지 모르겠다.

 

그래서 비효율적으로라도 풀어보려 한다.

경계값과 왔던 길 체크만 하여 규칙 없이 푼다.

최대 길이 30이기에 통과는 할 것이다.

 

으, 이것도 실패. nx, ny의 좌표를 어찌 이용할지 모르겠다.

#include <string>
#include <vector>
#include <array>

using namespace std;

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer(n, vector<int>(n, 0));
    int dir = 1;
    int x = 0, y = 0;
    int nx = x * dir;
    int ny = y * dir;
    int num = 1;

    for (int loop = 1; loop <= n * n;)
    {
        while (0 <= nx && n > nx && 0 == answer[ny][nx])
        {
            x = nx;
            answer[y][x] = loop++;
            nx = x * dir + 1;
        }

        nx = x * dir;

        while (0 <= ny && n > ny && 0 == answer[ny][nx])
        {
            y = ny;
            answer[y][x] = loop++;
            ny = y * dir + 1;
        }

        ny = y * dir;

        if (!(loop & 1))
        {
            dir *= -1;
        }
    }

    return answer;
}

도와줘 제미니!

 

내껀 조건에 맞으면 이동이었는데, 얘는 조건에 맞지않으면 방향 전환.

그리고 네방향 x2 를 배열로 만들었다.

 

방향을 잡고 길을 가야하는 문제는 이렇게 푸는 게 낫겠다.

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer(n, vector<int>(n, 0));

    int num = 1;
    int x = 0, y = 0;
    int dx[] = {1,0,-1,0};
    int dy[] = { 0,1,0,-1 };
    int dir = 0;

    while (num <= n * n)
    {
        answer[y][x] = num++;
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (0 > nx || n <= nx || 0 > ny || n <= ny || 0 != answer[ny][nx])
        {
            dir = (dir + 1) % 4; //경계 또는 지나온 길이라면 방향 전환.
            nx = x + dx[dir];
            ny = y + dy[dir];
        }

        x = nx;
        y = ny;
    }

    return answer;
}

 

이전의 c코드와 비교하면,

이전은 규칙성을 찾아 해결했으나 유연성과 가독성이 안좋았다.

성능상의 차이도 없이 둘다 O(N)이기에 이 방법을 익히는 게 범용적으로 좋을 것 같다.