[C++]백준(BOJ) - 2056 소용돌이 예쁘게 출력하기(시뮬레이션)

난이도 : 골III

풀이 시간 : 1시간 이상

알고리즘 유형 : 구현

풀이 방법 : 방향을 바탕으로 구현, 크기 만큼 공백 출력

 

문제 예시

모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 

 

숫자 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는 가장 오른쪽 아래 칸이다.
-> 행렬 구하기

 

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

 

문제 풀이 방식

이 문제는 구현이기 때문에 하나씩 살펴보겠습니다.

일단 메모리가 128MB이기 때문에 달팽이 수열을 간단하게
10000x10000 으로 하는 것은 메모리 초과를 발생합니다.

• 0 ≤ r2 - r1 ≤ 49
• 0 ≤ c2 - c1 ≤ 4

를 이용한다면 r2 - r1 최대값 = 50, c2 - c1 최대값 = 4이기 때문에

최대 board[51][5]로 메모리를 아껴줄 수 있습니다.

 

그리고 수열을 direction 방향으로 돌아주면 됩니다. 

 

 

안에 들어가 있다는 범위는 x, y 값을 순회하면서

r1, r2 c1, c2의 범위를 비교하면서 x, y가 범위 안에 있다면 board[x - r1][y - c1]  안에 넣어줍니다.

 

이렇게 반복한다면 board의 값을 구하고 가장 큰 자리수를 확인합니다. 

가장 큰 자리수를 기준으로 공백을 처리하며 마무리 됩니다.

 

아래는 코드입니다.

#include <iostream>
#include <string>
#include <iomanip>
#define MAX 10001

using namespace std;

int board[51][5] = { 0, };
// 오, 위, 왼, 아
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0, -1, 0 };


int main() 
{
    ios::sync_with_stdio(0);
	cin.tie(0);
    
	int r1, c1, r2, c2;

	cin >> r1 >> c1 >> r2 >> c2;

	int size = 1, cnt = 1;
    int cur = 0, dir = 0;
	int x = 0, y = 0;

	if (r1 <= x && x <= r2 && c1 <= y && y <= c2)
		board[x - r1][y - c1] = cnt;
	
	++cnt;

	while (board[0][0] == 0 || board[r2 - r1][0] == 0 ||
    board[r2 - r1][c2 - c1] == 0 || board[0][c2 - c1] == 0) 
	{
		x += dx[dir], y += dy[dir];

		if (r1 <= x && x <= r2 && c1 <= y && y <= c2) 
			board[x - r1][y - c1] = cnt;

		++cnt;
		++cur;

		if (cur == size) 
		{
			cur = 0;
			++dir;
			dir %= 4;

			if (dir == 0 || dir == 2)
				++size;
		}
	}

	int space = to_string(cnt).size();

	for (int i = 0; i <= r2 - r1; i++) 
	{
		for (int j = 0; j <= c2 - c1; j++)
		{
        	    int size = space - to_string(board[i][j]).size();
		    for(int k = 0; k < size; ++k)
			    cout << ' ';

		
			cout << board[i][j] << ' ';
		}

		
		cout << '\n';
	}

	return 0;
}