BOJ - 1022번 소용돌이 예쁘게 출력하기, 구현 문제 (with C++)

이번에 풀이한 1022번 소용돌이 예쁘게 출력하기 문제는 구현 유형의 문제로, 제가 구현 문제 풀이에 취약한 것 같아서 풀게 되었습니다. 

 

😂 문제 링크 

1022번: 소용돌이 예쁘게 출력하기

 

😁 문제 설명

 

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

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

출처: acmicpc.net

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

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

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

😎 입력

 

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

 

😎 출력

 

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

 

😖 풀이 설명

 

우선 구현 문제를 많이 안풀어버릇 하다 보니 다른 분들의 풀이를 많이 참고해서 문제를 풀었습니다. 문제 풀이의 핵심 아이디어는 1000 x 1000 크기의 배열에 대한 메모리 할당이 불가능하고, 시간 또한 오래 걸리기 때문에 우리가 구하고자 하는 범위((r1, c1) ~ (r2, c2))내에 해당하는 값만을 배열에 저장해서 결과물로 만들어내자! 입니다.

 

또한 소용돌이 배열의 특징을 보면 총 4개의 방향으로 숫자가 증가하며 기록되는데, 이 방향이 두 번 바뀔 때마다 해당 방향으로 뻗어가는 길이가 1씩 증가하는 특징을 확인할 수 있었습니다. (다른 분들의 풀이를 참고해 아이디어를 얻었습니다.)

 

예를 들면 1 -> 2 -> 3 -> 4, 5 -> 6, 7 -> 8, 9, 10 -> 11, 12, 13 -> 14, 15, 16, 17 -> 18, 19, 20, 21 ->...

이런 식으로 방향이 바뀌면서 소용돌이 배열을 그리게 됩니다. 

 

😜 소스 코드 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX 10001

using namespace std;

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


int main() {
	int r1, c1, r2, c2;

	/*
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> r1 >> c1 >> r2 >> c2;
	*/
	scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
	int len = 1;
	int cnt = 1;
	
	int x = 0, y = 0;
	if (r1 <= x && x <= r2 && c1 <= y && y <= c2) {
		arr[x - r1][y - c1] = cnt;
	}
	cnt++;

	int curLen = 0;
	int dir = 0;

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

		// 범위 내의 결과만 배열에 담는다.
		if (r1 <= x && x <= r2 && c1 <= y && y <= c2) {
			arr[x - r1][y - c1] = cnt;
		}

		cnt++;
		curLen++;

		if (curLen == len) {
			curLen = 0;
			dir++;
			dir %= 4;

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

	int space = 0;
	while (cnt != 0) {
		cnt /= 10;
		space++;
	}
	//cout << space << "\n";

	for (int i = 0; i <= r2 - r1; i++) {
		for (int j = 0; j <= c2 - c1; j++) {
			/*
			cout.width(space);
			cout << std::right << arr[i][j] << " ";
			*/
			printf("%*d ", space, arr[i][j]);
		}
		printf("\n");
	}

	return 0;
}

/*
같은 길이로 두 번 갈 때마다 길이가 1씩 증가한다.
방향은 매번 바뀐다.
-> ^ <- v 순서대로
*/