[백준 1022번] 소용돌이 예쁘게 출력하기

문제 링크

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

 

문제 요약

반시계 방향을 따라 소용돌이 모양으로 숫자를 채운 뒤, 주어진 범위의 숫자를 포맷에 맞게 출력하는 문제

 

문제 풀이

이 문제를 푸는 방법에는 실제로 소용돌이를 만들어보는 시뮬레이션 방법과 특정 좌표의 숫자를 구할 수 있는 규칙을 찾는 방법 두 가지가 있다. 이 문제를 풀기 위해 접근할 때 보통 두 번째 방법을 많이 생각하는 것 같다. 하지만 입력으로 주어지는 수의 제한 범위와 현대 컴퓨터의 연산속도를 이용하면 직접 시뮬레이션을 돌려 푸는 방법도 있다는 것을 소개하고 싶다.

풀이 1. 시뮬레이션

모눈종이에 소용돌이 모양으로 숫자를 채우는 시물레이션을 돌려보는 상상을 해보자. 입력으로 주어지는 좌표의 최솟값은 -5,000이고 최댓값은 5,000이다. 입력으로 주어지는 좌표의 최솟값은 -5,000이고 최댓값은 5000이다. 따라서 우리가 시뮬레이션을 돌려봐야 하는 모눈종이 한 변의 길이는 최대 10,000이 된다. 한 변의 길이가 10,000인 모눈종이에 소용돌이 모양으로 숫자를 채우기 위해 반복문을 돌아야 하는 횟수는 10,000의 제곱인 1억 번이다. 이 정도 횟수는 반복문 안에 무거운 작업만 들어가지 않는다면 2초 내에 충분히 수행할 수 있는 연산량이다. 시뮬레이션으로 풀 수 있다는 것을 알았으니 실제 구현을 어떻게 할지 생각을 해보자.

 

(0, 0)에서 시작하여 소용돌이 모양으로 좌표를 움직이기 위해 방향 배열 \(dr\), \(dc\)를 준비한다. 이 방향 배열은 현재 좌표 \((r, c\))가 다음에 어디로 움직여야 할지 알려주는 이정표 역할을 한다.

const int dr[] = {0, -1, 0, 1};
const int dc[] = {1, 0, -1, 0};

방향 배열을 사용하여 현재 좌표가 움직일 수 있는 방향은 총 네 가지다. 이 방향은 특정한 좌표에 도달하면 다음 인덱스 방향으로 바뀌게 된다. 그 순간은 직접 소용돌이를 그려보면 쉽게 찾아볼 수 있다.

 

방향을 바꿔야 하는 순간들

소용돌이를 그리면서 방향을 바꿔야 하는 좌표에 네모 표시를 해줬다. 같은 색의 네모들의 좌표는 열과 행의 절댓값 중 더 큰 값이 모두 같다. 이 특징을 이용하면 현재 좌표가 방향을 바꿔야 하는 좌표인지 알 수 있다.

r += dr[k];
c += dc[k];

int mmax = max(abs(r), abs(c));
        
if ((mmax - 1 == r && mmax== c)
    || (-mmax == r && mmax == c)
    || (-mmax == r && -mmax == c)
    || (mmax == r && -mmax == c)) {
        // k는 방향 배열에서 어떤 인덱스를 선택할지 결정하는 변수
        k = (k + 1) % 4;
}

 

소용돌이 모양으로 채운 숫자를 모두 저장하기에는 메모리가 부족하기 때문에 출력에 필요한 좌표를 map에 저장하는 방법을 사용한다. 현재 좌표가 내가 출력해야 하는 좌표에 포함되면 map에 저장!!

 

출력할 때는 가장 큰 숫자의 자릿수를 계산해 주고 C++의 setw 기능을 이용해 예쁘게 출력해야 하는 조건을 맞춰주자. 이렇게 구현한 최종 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;

map<pair<int, int>, int> ans;

int r1, c1, r2, c2, maxLen;
const int dr[] = {0, -1, 0, 1};
const int dc[] = {1, 0, -1, 0};

int main() {
    cin >> r1 >> c1 >> r2 >> c2;
    
    int r = 0, c = 0, cur = 1, k = 0;
    while (ans.size() != (r2 - r1 + 1) * (c2 - c1 + 1)) {
        if (r1 <= r && r <= r2 && c1 <= c && c <= c2) {
            ans[{ r, c }] = cur;
            maxLen = floor(log10(cur)) + 1;
        }
        
        r += dr[k];
        c += dc[k];
        
        int mmax = max(abs(r), abs(c));
        
        if ((mmax - 1 == r && mmax== c)
            || (-mmax == r && mmax == c)
            || (-mmax == r && -mmax == c)
            || (mmax == r && -mmax == c)) {
            k = (k + 1) % 4;
        }
    
        ++cur;
    }
    
    for (int r = r1 ; r <= r2 ; ++r) {
        for (int c = c1 ; c <= c2 ; ++c) {
            cout << setw(maxLen) << ans[{ r, c }];
            
            if (c < c2) {
                cout << " ";
            }
        }
        
        cout << endl;
    }
}

---

풀이 2. 규칙 찾기

소용돌이 모양의 숫자들은 특정 기준에 따라 그룹 지을 수 있다. 각 숫자의 열과 행의 절댓값 중 더 큰 값이 똑같은 숫자들끼리 그룹을 지어보자.

그룹지을 수 있는 숫자들

같은 그룹의 숫자들에게는 같은 레벨을 부여할 수 있다. 각 레벨은 \((0, 0)\)에서의 거리로 정의할 수 있으며, \((0, 0)\)에서 멀어질수록 레벨은 1씩 증가한다. 편의상 레벨은 1부터 시작하며, \((0, 0)\)은 그룹에 포함시키지 않고 예외 처리를 할 예정이다.

int getLevel(int r, int c) {
    return max(abs(r), abs(c));
}

각 그룹에 레벨을 부여하면, 각 레벨까지 등장한 숫자의 개수를 계산할 수 있다. 각 그룹은 한 변의 길이가 \((level + 1) * 2 - 1\)인 정사각형이며, 이 정사각형의 면적을 구하면 해당 레벨까지의 숫자 갯수를 알 수 있다.

int getBiggestValueOf(int level) {
    int len = (level + 1) * 2 - 1;
    
    return len * len;
}

이제 한 그룹을 조금 다 자세히 들여다보자. 각각의 그룹들은 다시 네 개의 서브 그룹(코드상에서는 step으로 부르려고 한다.)으로 나눌 수 있다.

한 그룹을 다시 네 개의 그룹으로 나눌 수 있다

한 개의 그룹은 총 \(level * 8\)개의 숫자로 이루어져 있으며, 이를 \(level * 2\)개의 숫자씩 총 네 개의 서브 그룹으로 다시 나눠줄 수 있다. 그룹 내의 어떤 숫자가 몇 번째 서브그룹에 속하는지는 조금 복잡하지만 행, 열, 레벨을 이용해 계산할 수 있다. 그리고 속한 서브그룹 내에서 몇 번째 순서인지도 같이 계산해준다.

 pair<int, int> getStepOfLevel(int r, int c, int level) {
    if (c == level && r >= -level && r <= level - 1) {
        return {1, abs(r - level)};
    } else if (r == -level && c >= -level && c <= level) {
        return {2, abs(level - c)};
    } else if (c == -level && r >= -level + 1 && r <= level) {
        return {3, abs(r - (-level))};
    } else if (r == level && c >= -level + 1 && c <= level) {
        return {4, abs(c - (-level))};
    }
    return {-1, -1};
}

지금까지 구한 정보로 특정 좌표 \((r, c)\)가 주어졌을 때 그 좌표에 들어가야 할 소용돌이 숫자를 상수시간에 계산할 수 있다.

int getValue(int r, int c) {
    if (r == 0 && c == 0) {
        return 1;
    }
    
    int level = getLevel(r, c);
    pair<int, int> step = getStepOfLevel(r, c, level);
    
    int biggestValueOfPrevLevel = getBiggestValueOf(level - 1);
    int cntOfPrevSteps = (step.first - 1) * (level * 2);
    
    return biggestValueOfPrevLevel + cntOfPrevSteps + step.second;
}

 

이제까지 구현한 코드들과 소용돌이를 이쁘게 출력하는 코드까지 합친 전체 코드는 다음과 같다.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int r1, c1, r2, c2, ans[110][110], maxLength;

int getLevel(int r, int c) {
    return max(abs(r), abs(c));
}

int getBiggestValueOf(int level) {
    int len = (level + 1) * 2 - 1;
    
    return len * len;
}

pair<int, int> getStepOfLevel(int r, int c, int level) {
    if (c == level && r >= -level && r <= level - 1) {
        return {1, abs(r - level)};
    } else if (r == -level && c >= -level && c <= level) {
        return {2, abs(level - c)};
    } else if (c == -level && r >= -level + 1 && r <= level) {
        return {3, abs(r - (-level))};
    } else if (r == level && c >= -level + 1 && c <= level) {
        return {4, abs(c - (-level))};
    }
    return {-1, -1};
}

int getValue(int r, int c) {
    if (r == 0 && c == 0) {
        return 1;
    }
    
    int level = getLevel(r, c);
    pair<int, int> step = getStepOfLevel(r, c, level);
    
    int biggestValueOfPrevLevel = getBiggestValueOf(level - 1);
    int cntOfPrevSteps = (step.first - 1) * (level * 2);
    
    return biggestValueOfPrevLevel + cntOfPrevSteps + step.second;
}

int main() {
    cin >> r1 >> c1 >> r2 >> c2;
    
    for (int r = r1 ; r <= r2 ; ++r) {
        for (int c = c1 ; c <= c2 ; ++c) {
            int val = getValue(r, c);
            int len = floor(log10(val)) + 1;
            maxLength = max(maxLength, len);
        }
    }
    
    for (int r = r1 ; r <= r2 ; ++r) {
        for (int c = c1 ; c <= c2 ; ++c) {
            int val = getValue(r, c);
            
            cout << setw(maxLength) << val;
            
            if (c < c2) {
                cout << " ";
            }
        }
        cout << endl;
    }
}

 

어떤 방법이 더 좋을까?

방법 1은 구현이 간단하지만, 모든 경우의 수를 계산해야 하기 때문에 시간이 오래 걸린다. 반면에 방법 2는 구현이 복잡하지만 특정 좌표의 값을 상수 시간에 알 수 있어 더 빠른 성능을 제공한다. 그렇다면 성능이 더 우수한 방법 2가 더 나은 알고리즘일까?

 

알고리즘 대회에서는 문제를 해결하는 것이 가장 중요하며, 성능이 떨어지더라도 제한시간 내에 답을 계산할 수 있다면 정답으로 인정된다. 따라서 방법 1과 방법 2 중 어느 것이 더 낫다고 쉽게 단정 지을 수는 없다. 만약 이 문제에서 주어진 좌표의 제한값이 더 컷다면 방법 1로는 풀 수 없었을 것이다. 하지만 문제의 제한값이 시뮬레이션을 이용해 충분히 해결할 수 있는 범위 내에 있었기 때문에 이 문제는 방법 1도 좋은 선택지 중에 하나다.

 

실전에는 어떤 문제가 어떤 조건으로 나올지 모른다. 그렇기 때문에 똑같은 문제더라도 가능한 많은 방법으로 풀어보는 것이 좋은 것 같다.