[백준 1022] - 소용돌이 예쁘게 출력하기(C++)[골드4]

문제

크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그러고 나서 0행 1열에 숫자 2를 쓴다. 거기서부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.

    -3 -2 -1  0  1  2  3
    --------------------
-3 |37 36 35 34 33 32 31
-2 |38 17 16 15 14 13 30
-1 |39 18  5  4  3 12 29
 0 |40 19  6  1  2 11 28
 1 |41 20  7  8  9 10 27
 2 |42 21 22 23 24 25 26
 3 |43 44 45 46 47 48 49

이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다.

예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.

1. 출력은 r1행부터 r2행까지 차례대로 출력한다.
2. 각 원소는 공백으로 구분한다.
3. 모든 행은 같은 길이를 가져야 한다.
4. 공백의 길이는 최소로 해야 한다.
5. 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
6. 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.

입력

첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다.

출력

r2 - r1 + 1개의 줄에 소용돌이를 예쁘게 출력한다.

 

문제 해석

배열의 크기가 굉장히 크기 때문에 메모리에 대해서 신경써야 합니다.
저도 무작정 모든 배열을 저장하고 해당 구간만큼 출력했는데, 메모리가 발목을 잡았습니다.

처참하네요..

 

제한

• -5 000 ≤ r1, c1, r2, c2 ≤ 5,000
• 0 ≤ r2 - r1 ≤ 49
• 0 ≤ c2 - c1 ≤ 4

 

우선 배열의 크기는 문제에서 주어진 제한만큼 배열을 만들어 주면 메모리초과를 피할 수 있습니다.

 

배열의 최대 크기는 [50][5]가 됩니다.

 

그래서 좌표를 계속 이동시켜주면서, 구간을 넘어가게 되면 자동으로 넘겨줍니다.

구간을 넘지 않는다면 숫자를 입력해줍니다.

 

즉 불필요한 배열저장을 넘기고, 구간내에 좌표들만 배열에 저장하면 메모리 초과를 피할 수 있습니다.

전부다 저장하기에는 메모리가 너무마 많이 잡아먹기 때문입니다.

 

 

음.. 손으로 그린점 참고해서 봐주세요..

우선 반시계 회오리는 오른쪽,왼쪽으로 진행할 때 이동할 수 있는 칸 수가 한 칸 늘어납니다.

이러한 점을 바탕으로 반시계 방향 회오리를 만들어주시면 됩니다.

이동칸수 만큼 이동했다면 방향 전화를 해주고, 방향이 왼쪽, 오른쪽일 경우 이동칸 수를 한 칸 늘려줍니다.

 

이렇게 코드를 다 짜니까 출력형식이 틀렸다고 하더라고요,,

문제를 보니 가장 큰 숫자 자리만큼 공백을 넣어줘야 한다길래,

가장 큰 수를 10으로 계속 나눠서 자리수를 증가시켜 주고, 그 자릿수만큼 공백을 포함해서 출력해 줬습니다.

 

 

💻코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int graph[50][5];
int r1, r2, c1, c2;
int num = 1;
int firstR, firstC = 0;
int x[4] = {0, -1, 0, 1};
int y[4] = {1, 0, -1, 0};
void make();
bool check();
int main()
{
    cin >> r1 >> c1 >> r2 >> c2; // r2>r1 // c2>c1  -r1~ r1의 소용돌이를 만들어야겟다.
    make(); //소용돌이 만들기
    //출력형식 맞추기.
    int degree=0;
    while(num){ //자리수 크기만큼 degree를 ++시킴.
        num/=10;
        degree++;
    }
    for (int i = 0; i <= r2 - r1; i++)
    {
        for (int j = 0; j <= c2 - c1; j++)
        {
            printf("%*d ",degree, graph[i][j]);
        }
        cout << endl;
    }
}
bool check()
{
    if (graph[r2 - r1][0] && graph[0][0] && graph[0][c2 - c1] && graph[r2 - r1][c2 - c1]) // 꼭짓점 다 채워지면 종료
    {
        return true;
    }
    else
        return false;
}
void make()
{
    int cnt = 0;
    int dir = 0;
    int move = 1;
    while (1)
    {
        if (check())
        { // 꼭짓점이 다 채워졋나
            break;
        }
        else
        {
            if (firstR - r1 >= 0 && firstR - r1 <= r2 - r1 && firstC - c1 >= 0 && firstC - c1 <= c2 - c1)
            {
                graph[firstR - r1][firstC - c1] = num;
            }
            cnt += 1;
            num++;
            firstR += x[dir],firstC += y[dir]; // dir : 오, 위 , 왼, 아
            // 4방향으로 돌려야하기에,
            if (move == cnt)
            {
                cnt = 0;
                dir = (dir + 1) % 4;
                if (dir == 0 || dir == 2) //왼쪽, 오른쪽
                {
                    move++;
                }
            }
        }
    }
}

코드 설명은 주석을 참고해주셉여

 

느낀 점

• 항상 알고리즘을 풀 때 메모리제한에 대해서 크게 신경 쓰지 않고 , 시간복잡도만 계산했었는데, 이번에 조금 된통 당했다,,
• 메모리제한만 신경 쓰면 쉽게 풀 수 있는 문제!