소용돌이 예쁘게 출력하기 (백준 1022)

(출처) https://www.acmicpc.net/problem/1022

📖 개요

위 그림과 같이 숫자 1로 (0,0) 좌표에서부터 시작하여 소용돌이치듯 점점 나아가는 식으로 맵을 채워줘야 하는 문제.

💡 소용돌이 패턴

문제에서 주어지는 소용돌이 패턴이란 우->상->좌->하 이동의 반복으로 이루어졌다.

따라서 (0,0) 좌표에서 시작하여 우,상,좌,하 순으로 이동한 뒤 다시 우로 돌아가는 패턴을 직접 구현해 주면 되는데, 특정 방향으로 정해진 이동횟수를 전부 이동한 경우에 이동방향이 변경될 수 있도록 구현해 주어야 한다.

이동횟수는 최초 (0,0) 좌표에서 시작해서 우 방향으로 1만큼 이동해야하고, 이후 상 방향으로 1만큼 이동해야한다. 그리고나서 좌 방향으로 2만큼, 하 방향으로 2만큼, 다시 우 방향으로 3만큼 이동한다.

과정을 반복하다 보면서 유심히 살펴보니 좌 방향으로 변할 때와, 다시 우 방향으로 돌아갈 때 이동해야하는 횟수가 +1씩 증가한다는 규칙이 존재한다는 것을 알 수 있었다.

따라서 해당 규칙을 추가해서 우상좌하 패턴을 구현해주었다.

👓 자세한 구현법

문제에서 주어지는 소용돌이 맵의 좌표 범위는 -5000 ~ 5000까지라서, 모든 맵을 2차원 배열로 표현하려면 array[10000][10000] 만큼 할당해 주어야만 했다.

배열로 약 1억개의 int형 요소를 보관하려면 대략 4억바이트 = 400mb의 메모리를 사용하게 되므로 메모리 초과(128mb 제한)가 예상됐다.

따라서 1부터 시작해서 1억까지 모든 소용돌이 맵을 그려나가되, 인풋 요구에 해당하는 범위의 수가 아니라면 pass시켜 버리면서 오로지 해당 범위의 수만 저장하는 식으로 로직을 진행하고자 했다.
(정확하게는 무한루프를 돌려 소용돌이를 만들어가면서 현재까지 배열에 저장된 수가 몇 개인지를 카운팅하여 필요한 수를 모두 저장한 경우에 루프를 종료시키는 식으로 코드를 짰다)

추가적으로는 소용돌이 맵을 나타내는 좌표와 return 시켜주기 위해 따로 생성한 맵(배열)의 인덱스가 서로 맞지 않기 때문에 배열 인덱스 값을 처리해 주는 과정을 추가해 주었고, 또한 값을 저장하면서 저장한 가장 큰 수의 자릿수가 얼마인지 기록하여 최종적으로 출력할 때 해당 자릿수에 맞춰서 공백 추가 처리를 해주도록 하였다.

💻 코드

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int r1,c1,r2,c2;
    cin >> r1 >> c1 >> r2 >> c2;
    vector<vector<int>> resultMap(r2-r1+1, vector<int>(c2-c1+1));
    int totalCoorNum = (r2-r1+1) * (c2-c1+1);
    int currentNum = 0, currentRow= 0, currentCol = 0;
    int discovered = 0, pattern = 0;
    int level = 1;  // level == 현재 패턴의 이동횟수 레벨. 패턴 변동시 remainedMoveCnt가 level 값에 맞게 충전됨.
    int remainedMoveCnt = 1; // remainedMoveCnt == 해당 패턴으로 이동해야하는 횟수. 0이 될시 패턴(방향) 변경
    int space = 0;


    int direction [4][2] = {{0,1}, {-1,0}, {0,-1}, {1,0}}; //우상좌하 순
    // 0,0 좌표부터 소용돌이를 그려가기 시작한다(무한루프로 돌림)
    // 루프를 돌면서 result로 반환해야하는 좌표를 지날때마다 resultMap에 좌표에 해당하는 값을 저장하고 discovered를 +1 증가시킨다. 발견해야하는 모든 좌표의 수에 discovered가 도달할 경우 루프를 종료시킨다.
    while(discovered != totalCoorNum) {
        currentNum++;
        if((r1 <= currentRow && currentRow <= r2) && (c1 <= currentCol && currentCol <= c2)) {
            discovered++;
            resultMap[currentRow-r1][currentCol-c1] = currentNum;
            int temp = currentNum / 10;
            int tempSpace = 0;
            while(temp != 0) {
                tempSpace++;
                temp /= 10;
            }
            if(tempSpace > space) space = tempSpace;
        }

        currentRow += direction[pattern][0];
        currentCol += direction[pattern][1];

        remainedMoveCnt--; //소용돌이 한칸 이동시키기
        if(remainedMoveCnt == 0) {
            pattern++;
            if(pattern == 4) {
                pattern = 0; //패턴 종료시 초기 패턴인 0으로 되돌리기
                level++;
            }
            if(pattern == 2) level++;
            remainedMoveCnt = level;
        }
    }

    for(int i = 0; i < r2 - r1 + 1; i++) {
        for(int j=0; j < c2 - c1 + 1; j++) {
            int temp = (*(resultMap.begin() + i))[j] / 10;
            int tempSpace = 0;
            while(temp != 0) {
                tempSpace++;
                temp /= 10;
            }

            for(int i = 0; i < space - tempSpace; i++) {
                cout << " ";
            }
            cout << (*(resultMap.begin() + i))[j];
            if(j != c2 - c1) cout << " ";
        }
        cout << endl;
    }

    return 0;
}