[프로그래머스/C++ 문제 풀이] Lv. 0 - 정수를 나선형으로 배치하기

 

문제 설명

양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

제한 사항

• 1 ≤ n ≤ 30

입출력 예시

N	Result
4	[[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
5	[[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]

 

입출력 예 #1

• 예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.

  1	2	3	4
  12	13	14	5
  11	16	15	6
  10	9	8	7

  따라서 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]를 return 합니다.

입출력 예 #2

• 예제 2번의 n의 값은 5로 5 × 5 배열에 다음과 같이 1부터 25까지 숫자를 채울 수 있습니다.

  1	2	3	4	5
  16	17	18	19	6
  15	24	25	20	7
  14	23	22	21	8
  13	12	11	10	9

  따라서 [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]를 return 합니다.

---

문제 풀이

N x N 크기의 배열에 값을 나선형으로 배치하기 위해 재귀함수를 사용해 문제를 해결하였습니다.

방향별 이동량(dx, dy)을 배열로 지정한 후 방향에 맞춰 다음 칸이 이동 불가능하면 다음 방향으로 이동하며 값을 채우는 방식으로 구현하였습니다.

 

> 방향별 이동량(dx, dy)을 배열로 지정

// 방향별 이동량 (우, 하, 좌, 상)
int dx[4] = 	{1, 0, -1, 0};
int dy[4] = 	{0, -1, 0, 1};

// 현재 진행중인 방향 (0 : 우, 1 : 하, 2 : 좌, 3 : 상)
int direction = 0;

 

> 모든 방향을 순서대로 순회하며 값 채우고 재귀 호출 

모든 방향(dx, dy)을 순회하며 이동 가능한 방향을 찾습니다. (우, 하, 좌, 상 순서)
for (int i = 0; i < 4; i++)
{
    // 다음 이동할 좌표를 구합니다.
    int nx = x + dx[(direction + i) % 4];
    int ny = y + dy[(direction + i) % 4];

    // 배열의 범위를 벗어난다면 건너뜁니다.
    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

    // 다음 칸이 존재하고, 아직 숫자가 안들어가 있는 경우
    if (v[ny][nx] == 0)
    {
        // 값을 채웁니다.
        v[ny][nx] = cnt;
			
        // 방향을 업데이트 하고 재귀 호출을 진행합니다.
        direction = (direction + i) % 4;
        Go(ny, nx, v, n, cnt + 1);
    }
}

 

정답 코드

#include <string>
#include <vector>

using namespace std;

//          우, 하, 좌, 상
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int direction = 0;

void Go(int y, int x, vector<vector<int>>& v, int n, int cnt){

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[(direction + i) % 4];
        int ny = y + dy[(direction + i) % 4];

        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

        if (v[ny][nx] == 0)
        {
            v[ny][nx] = cnt;

            direction = (direction + i) % 4;
            Go(ny, nx, v, n, cnt + 1);
        }
    }
}

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

    // 크기 조정
    answer.resize(n);
    for (int i = 0; i < n; i++)
    {
        answer[i].resize(n);
    }

    answer[0][0] = 1;

    // 숫자 넣기
    Go(0, 0, answer, n, 2);

    return answer;
}