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

문제

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 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는 가장 오른쪽 아래 칸이다.

출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1022)

풀이

소용돌이를 그려가는 규칙을 찾아서 while문을 돌며 map에다가 기록을 한다음 가장 왼쪽 위 칸, 아래 칸, 가장 오른쪽 위 칸, 아래 칸이 다 채워질 경우 while문에 빠져나와서 예쁘게 출력하면 됩니다.

처음 문제 풀 때는 메모리 제한을 고려하지 않아서 r1, c1, r2, c2가 들어왔을 때 가장 큰 절대값을 n으로 두고 (2*n)*(2*n)의 배열을 만들었더니 절대값이 5000이 들어오는 경우 10000*10000 이므로 바로 메모리를 초과해버렸습니다. 입력조건을 자세히 살펴보면 r2-r1은 49보다 작거나 같고 c2-c1은 4보다 작거나 같기 때문에 (r2-r1)*(c2-c1) 만큼만 배열을 만들면 메모리를 낭비하지 않을 수 있습니다! 

전체 소용돌이를 위한 배열을 만들지 않고 어떻게 소용돌이를 그릴지 고민을 해보았습니다. (0, 0) 에서 소용돌이를 시작해야하므로 x, y값은 실제 소용돌이가 치는(음수를 포함하는) 좌표를 뜻하게 구현했습니다. 그런데 출력을 위해 할당한 map에 그리기 위해서는 음수를 포함하는 좌표를 사용할 수 없으므로 (x-r1, y-c1) 로 값을 계산해주어서 기록을 해야하는 (0, 0) ~(r2-r1, c2-c1) 으로 매칭이 합니다. 따라서 x-r1 한 값이 0보다 크거나 같고, r2-r1보다 작거나 같은 경우와 y-c1 한 값이 0보다 크거나 같고, c2-c1보다 작거나 같은 경우를 만족한다면 기록을 해야하는 범위이므로 이때 map에 해당하는 소용돌이 번호를 기록해줍니다!

또한 소용돌이치는 규칙을 살펴보면 총 4방향으로 돌고 있는데 방향이 두번 바뀔 때마다 한 방향에서 전진해야하는 카운트가 증가합니다. 이 규칙을 통해서 방향을 바꿔주며 좌표를 갱신해주면 됩니다. 가장 외각의 4좌표가 다 채워졌을 경우에는 더이상 소용돌이를 치지 않고 출력하면 되므로 그렇게 구현해주었습니다.

코드

#include<iostream>

#include<cstdio>

#include<stdlib.h>

using namespace std;

int dx[4] = {-1, 0, 1, 0};

int dy[4] = {0, -1, 0, 1};

int main(){

int r1, c1, r2, c2;

int x, y, n, dir, next, cnt, dcnt, num;

int map[50][5];

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

for(int i=0; i<=r2-r1; i++){

for(int j=0; j<=c2-c1; j++)

map[i][j] = 0;

}

x = y= 0;

dir = 3;

dcnt = num = 1;

cnt = 0;

while(!((map[0][0] != 0 ) && (map[0][c2-c1] != 0 ) && (map[r2-r1][0] != 0 ) && (map[r2-r1][c2-c1] != 0))){

if(x-r1 >=0 && x-r1 <= (r2-r1) && y-c1 >=0 && y-c1 <= (c2-c1)){

map[x-r1][y-c1] =num;

}

num++;

cnt++;

x = x+dx[dir];

y = y+dy[dir];

if(cnt == dcnt){

cnt=0;

dir = (dir+1)%4;

if(dir == 3 || dir == 1)

dcnt++;

}

}

cnt=0;

while(num > 0){ 

num /= 10;

cnt++; //출력폭을 찾기 위해서

}

for(int i=0; i<=(r2-r1); i++){

for(int j=0; j<=(c2-c1); j++)

printf("%*d ",cnt, map[i][j]);

printf("\n");

}

return 0;

}