[Programmers] 정수를 나선형으로 배치하기

 

 

프로그래머스

Lv. 0
정확성 테스트 100%

---

풀이

$n \times n$짜리 배열에 1부터 $n * n$까지의 정수값을 나선형으로 저장하는 문제이다.

문제의 예제를 보면 어떤 식인지 직관적으로 이해가 되지만 바로 방법을 떠올리긴 힘들 수 있다.

 

방법은 아래와 같다.

1. $num = 1$부터 $n \times n$배열 result의 탐색을 시작한다.
2. $num \leq n * n$가 성립하는동안 num++하며 아래를 반복한다.
   1. 벽을 만날때까지 직진하며 num을 result에 저장한다.
   2. 벽을 만난다면, num의 직진 방향을 시계방향으로 90도 꺾어준다.

여기서 "벽"이란 배열의 끝(0, n-1) 혹은 이미 값이 채워진 부분을 뜻한다.

DFS, BFS 문제를 자주 풀어봤다면 벽이란 표현이 익숙할 것이다.

 

그리고 벽을 만났을 때 진행방향을 시계방향으로 바꿔주기 위해 모듈러(%)를 이용한 수의 구간성이란 개념을 사용했으니 이 글을 한번 읽어보길 추천한다.

#include <vector>
#include <array>

using namespace std;

array<int, 4> dy = { 0,1,0,-1 };
array<int, 4> dx = { 1,0,-1,0 };

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

    int y = 0;
    int x = 0;
    int dir = 0;

    int num = 1;
    while (num <= n * n)
    {
        result[y][x] = num++;

        int ny = y + dy[dir];
        int nx = x + dx[dir];

        if (ny < 0 || ny >= n || nx < 0 || nx >= n || result[ny][nx] != 0)
            dir = (dir + 1) % 4;

        y += dy[dir];
        x += dx[dir];
    }
    return result;
}

(0, 0)부터 시작해서 순차적으로 num을 저장해주는데, 만약 다음에 갈 좌표가 맵 밖이거나, 이미 값이 채워진 곳이라면 방향을 바꾸도록 하였다.