[C++][백준 1913] 달팽이

https://www.acmicpc.net/problem/1913

풀이

실제로 사람이 채워나가듯 빙글빙글 돌며 2차원 배열을 채운다.

직접 해당 그림을 그려보다 발견한 규칙들이다

가장 큰 수(n^2)부터 시작해서 하나씩 수를 줄여나가며 채워나간다고 했을 때

1. 채워나가는 순서는 아래쪽, 오른쪽, 위쪽, 왼쪽 순으로 반복된다

2. (처음을 제외하고) 방향이 바뀌기까지의 수가 방향이 두 번 바뀔 때마다 1씩 줄어든다

 

위 규칙을 이용해 코드를 작성하였다(문제에서 n은 홀수라고 나와있었기 때문에 홀/짝수에 따라 초기값을 다르게 세팅할 필요가 없었다)

 

1. n * n 부터 시작해서 row 0, col 0의 위치에서부터 아래방향으로 채워나간다

2. 하나씩 채울 때마다 count를 세 주다가, 방향이 바뀌어야 하는 시점에 도달했으면 방향을 바꾸고, 방향을 바꾼 횟수 count를 세 준다

3. 만약 방향을 바꾼 횟수가 (처음 제외) 2번이 되면 방향을 바꾸어야 하는 시점을 1만큼 줄인다

 

제출 코드

#include <iostream>
using namespace std;

int arr[1000][1000];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, find;
    cin >> n >> find;
    int num = n * n + 1; // 배열에 넣을 숫자
    int row = 0; int col = 0; // row, col 좌표
    int dir = 0; // 방향
    int cnt = 0; int dirCnt = 1;
    int s = n; // 방향을 바꿔야 하는 시점
    int coord[2];

    while(--num)
    {
        if (num == find) { coord[0] = row + 1; coord[1] = col + 1; }
        arr[row][col] = num;

        if (++cnt == s)
        {
            dir = (dir == 3 ? 0 : dir + 1);
            dirCnt++;
            cnt = 0;
        }
        if (dirCnt > 1)
        {
            s--;
            dirCnt = 0;
        }

        switch (dir)
        {
        case 0: // down
            row++; break;
        case 1: // right
            col++; break;
        case 2: // up
            row--; break;
        case 3: // left
            col--; break;
        default: break;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << arr[i][j] << " ";
        cout << '\n';
    }

    cout << coord[0] << " " << coord[1];
}

배열의 크기가 커 전역변수로 지정하였다