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

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

 

난이도 : 골드 3 
알고리즘 유형 : 구현, 수학 
풀이 시간 : 54분 

문제 풀이 

`(0, 0)`에서 시작하여 반시계 방향으로 소용돌이 도는 숫자 배열의 특정 부분을 출력하는 문제다.

여기서 생각해야 할 부분이 있다면, 배열의 범위가 $-5000 ≤ r1, r2, c1, c2 ≤ 5000$이기 때문에 (0, 0)이 배열의 왼쪽 위가 아니다. 따라서 초기에 $r1, c1$ 좌표를 `(0, 0)`으로 맞춰줄 필요가 있다.

// 초기 1 위치 잡아주기
int r = -r1; int c = -c1;
r2 += -r1 + 1; r1 = 0;
c2 += -c1 + 1; c1 = 0;

 

이후, 배열 범위의 숫자가 다 채워질 때까지 while문을 돌려준다. 

여기서 소용돌이로 출력하는 부분에 대해서 자세히 설명하자면, 오른쪽, 위쪽으로 갈 때와 아래, 왼쪽으로 갈 때마다 갈 수 있는 칸이 한 칸씩 증가한다. 따라서 이 부분을 `check_dir`로 계산해준 다음, 왼 / 오른쪽 칸이 올 때마다 이동할 칸을 한 칸씩 늘려주었다.

 

코드

/*
- r1행부터 r2행까지 차례대로 출력한다
- 각 원소는 공백으로 구분함
- 모든 행은 같은 길이를 갖는다
- 공백의 길이는 최소로 해야한다
- 모든 숫자 길이는 같아야한다
- 수의 길이가 가장 길이가 긴 수보다 작다면 왼쪽부터 공백삽입
	- 오른쪽으로 정렬

풀이:
구현
배열이 10000 x 10000이기 때문에 공간복잡도 생각해야한다
	-> 배열에 먼저 값 넣어두면 멤초남
일단 입력부터 받고, 출발지, 도착지 생각하기
범위 넘어가는 값이면 출력종료하기
*/

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

bool check_(int r, int c) {
	return r1 <= r && r < r2 && c1 <= c && c < c2;
}

int main() {
	cin >> r1 >> c1 >> r2 >> c2;
	// 방향 세 번 틀었으면, 그다음 방향은 한 칸씩 더 가주기
	// 여기서 한 번 더 간 것도 방향에 추가해야된다.

	// 초기 1 위치 잡아주기
	int r = -r1; int c = -c1;
	r2 += -r1 + 1; r1 = 0;
	c2 += -c1 + 1; c1 = 0;
	vector<vector<int>> grid(r2 - r1, vector<int>(c2 - c1));
	int cnt = 0;
	int check_dir = 0; int move = 1;
	int d = 3;	// 무조건 오른쪽부터 이동한다.
	int number = 1;
	int nr, nc;
	if (check_(r, c)) {
		grid[r][c] = 1;
		cnt++;
	}
	// 배열 탐색 시작
	while (cnt < (r2 - r1) * (c2 - c1)) {
		d = (d + 1) % 4;
		check_dir++;
		if (check_dir > 2) {
			check_dir = 1;
			move++;
		}
		for (int i = 0; i < move; i++) {
			number++;
			nr = r + dr[d];
			nc = c + dc[d];
			if (check_(nr, nc)) {
				grid[nr][nc] = number;
				cnt++;
			}
			r = nr;
			c = nc;
			if (cnt >= (r2 - r1) * (c2 - c1))
				break;
		}
	}

	// 자릿수확인
	string last_number = to_string(number);
	for (int i = 0; i < r2; i++) {
		for (int j = 0; j < c2; j++) {
			string tmp = to_string(grid[i][j]);
			while (tmp.size() != last_number.size())
				tmp = ' ' + tmp;
			cout << tmp << ' ';
		}
		cout << '\n';
	}

	return 0;
}

배운 점 

출력 부분에서 `int`형을 `string`으로 변환해주는 파싱 작업이 익숙하지 않아 검색해보았다. 검색해보니 `#include <string>`의 `to_string()` 메서드를 사용하여 간단하게 변환해줄 수 있었다.

파싱은 어려워 ㅜㅜ