백준 알고리즘 1022번. 소용돌이 예쁘게 출력하기 소스 및 해설

빙글 빙글~ 세상은 어지럽지만 그가운데 고요하고 돌지 않는 곳이 있지요.

마치 태풍의 눈처럼 말입니다.

 

비록 저 높은 절벽으로부터 폭포가 쏟아지는 가운데 있지만,

그 뒷편에 아주 안전한 장소에서 보살핌을 받는 어린 새처럼

하나님을 신뢰하고 의지하는 사람들 또한 하나님께서 지키시고,

하나님께서는 그러한 사람들을 끝까지 포기하지 않고

저 천국으로 인도하실 수 있는 분이심을 믿습니다 :)

 

여호와께서 그를 황무지에서,

짐승의 부르짖는 광야에서 만나시고

호위하시며 보호하시며

자기 눈동자같이 지키셨도다

( 성서 신명기 32장 10절 말씀 )

 

이번 백준 알고리즘 문제는 빙글 빙글 소용돌이가 돌아가는 순서대로 숫자를 매겨서 표시하는 문제인데요. 은근히 함정들이 있더라구요.

​

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

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

 

단순히 출력결과만 보고 단순하다고 단정짓기엔 이릅니다.

출력형식실패란 함정과, 마지막 함정에서 크레이는 꽤 헤멨거든요 :)

​역시 이론적인 부분 설명 위주로 그리고 해당 이론을 적용한 소스를 공개해드리겠습니다.

​

처음에 0,0 좌표에 숫자 1을 씁니다.

그리고 그 다음부터 다음과 같은 규칙을 따릅니다.

오른쪽으로 1칸 이동하고 다음 숫자 2를 쓰고,

위쪽으로 1칸 이동하고 다음 숫자 3을 씁니다.

다시 왼쪽으로 2칸 이동하면서 연속으로 숫자 4, 5를 쓰고

다시 아래로 2칸 이동하면서 연속으로 숫자 6, 7을 씁니다.

이런식으로 연속으로 이동하는 칸수를 2라인마다 돌아가면서, 한 칸 씩 늘려서 계속 반복하는 것이지요.

그러면 이렇게 됩니다.

 

조금 어려운 부분으로는 표시영역이 제한이 있다는 점입니다.

조건설명을 잘 읽어서 이해해보면 가로로 최대 5칸, 세로로 최대 50칸의 영역까지만 표시하는 것을 볼 수 있습니다. 그렇기 때문에 가로배열 크기는 5로 정의하면 족합니다.

​

배열을 미리 정의해두고 그 범위 안에 배열이 위치할때만 숫자를 입력해야 하는데요.

크레이는 배열 입력 부분은 함수화해서 소스와 생각할 부분을 일부 단순화하였습니다.

​

이 문제의 첫번째 함정을 알려드리면 숫자 범위가 매우 크다는 것입니다.

수치의 범위는 문제에 언급되어 있지 않지만, 소용돌이는 바퀴를 돌면 돌수록 점점 범위가 커지기 때문에 좌표의 범위가 -5000 ~ 5000이라는 것으로 보아, 매우 큽니다.

int 형으로는 우선 확실히 처리가 안됩니다.

최소한 long 형으로 해야 문제가 풀리더군요. 최소 0이 8개는 붙는 것으로 보입니다.

​

그리고 마지막 문제 데이터 또한 함정인데요. 크레이의 추리상

분명히 데이터가 0 0 0 0 입니다.

크레이는 1칸이 채워질때마다 채워진 숫자를 더해서 모두 차면 끝나도록 짰는데

마지막 99%에서 계속 시간 초과가 나더라구요.

​

첫번째 0,0 좌표에 숫자 1을 넣고 바로 검사를 하지 않았는데 그 때문에 이후로는 무한 루프에 빠지는 것으로 보여서, 첫번째에 숫자를 넣고 바로 검사하는 부분을 추가하니 문제가 풀렸습니다.

​

주석을 자세히 달아 드리니 이해하시는데 조금이라도 도움 되시길 바랍니다 :)

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

// == 전역변수로 정의하는 이유는 속도를 위해서
// 전역변수로 숫자를 쓸 공책 정의
long map[50][5];
// 범위 정의
int c1, c2, r1, r2;
// 채워져야할 숫자 갯수
int box = 0;// 채워진 갯수
int fillcount = 0;	

// 숫자를 넣고, 꽉참 여부를 반환
bool pixel(int x, int y, int number)
{
	// 채워져야 하는 칸의 범위가 아니라면 아무 것도 안 합니다.
	if (x < c1 || x > c2 || y < r1 || y > r2)return false;
	// map 공책에 숫자를 하나씩 적습니다.
	map[y-r1][x-c1] = number;
	// 채워진 갯수를 하나 증가하고
	fillcount++;
	// 모두채워졌다면 그 싸인으로 true 를 반환합니다.
	if (fillcount >= box)return true;
	// 모두 안 채워졌다면?  false 를 리턴합니다.
	return false;
}

void Result() {
     
	// 범위 입력
    scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
	// 채워질 숫자 갯수 계산
    box = (r2 - r1 + 1) * (c2 - c1 + 1);
    // 초고속 메모리 초기화!
    memset(map, 0, sizeof(long) * 50 * 5);
	// 1부터 시작한다
    long num = 1;
	// 좌표는 0, 0 부터 시작
    int x = 0, y = 0;
	//
    int dir_target = 1;	// 처음에는 1칸 이동
    bool full = false;
	// 0,0 좌표에 숫자1을 넣고 바로 꽉 찼는지 검사합니다.
    full = pixel(0, 0, num);
	// 꽉 차지 않았다면 무한 반복
    while ( full == false ) {
        // 오른쪽으로 이동
		// Y좌표가 범위 밖에 있으면 검사하나 마나이므로 
		// 시간단축을 위해 X좌표 이동과 대입 숫자를 한꺼번에 증가합니다.
		// 이 부분이 있어서 엄청나게 시간이 단축됩니다.
		if(y < r1 || y > r2) { x+=dir_target; num+=dir_target; }
		// Y 좌표가 범위 안에 있으면 대입될 가능성이 있으므로
		else {
			// 이동량만큼 한칸씩 이동하면서 ( 맨 처음에는 1 )
			for (int i = 0; i < dir_target; ++i) 
				// pixel 함수를 호출하여 숫자 대입을 시도합니다.
				// 그러다 모든 숫자가 꽉 차면 full 값이 true 가 되고 for 문이 중지됩니다.
				if( (full = pixel(++x, y, ++num))==true) break;
			// 꽉 찼다면 무한 루프를 빠져나갑니다.
			if (full == true)break;
		}

        // 위쪽으로 이동
		// X좌표가 범위 밖이면, 마찬가지로
		// Y좌표와 대입 숫자를 한꺼번에 이동
		if(x < c1 || x > c2) { y-=dir_target; num+=dir_target; }
		// 그 외라면
		else {
			// 역시 이동량만큼 한칸씩 이동하며
			for (int i = 0; i < dir_target; ++i) 
				// 숫자를 넣으면서 꽉참여부를 검사합니다.
				if( (full = pixel(x, --y, ++num))==true) break;
			// 꽉차면? 무한루프를 빠져나가는 것이지요.
			if (full == true)break;
		}

		// 오른쪽, 위쪽으로 한번, 한번 이동한 다음에는 이동량을 1 증가합니다.
        dir_target++;

        // 왼쪽		
		// 반복 설명은 피하겠습니다 :) 
		// 앞과 똑같은데 방향만 왼쪽입니다.
		if(y < r1 || y > r2) { x-=dir_target; num+=dir_target; }
		else {
			for (int i = 0; i < dir_target; ++i)
				if( (full = pixel(--x, y, ++num))==true) break;
			if (full == true)break;
		}

		// 아래
		// 4번째 턴에는 아랫방향!
		if(x < c1 || x > c2) { y+=dir_target; num+=dir_target; }
		else {
			for (int i = 0; i < dir_target; ++i)
				if( (full = pixel(x, ++y, ++num))==true) break;			
			if (full == true)break;
		}

		// 역시 왼쪽, 아랫쪽으로 이동한 다음에 이동량을 1 증가합니다.
		dir_target++;
    }

	// 그 다음으로는 예쁘게 출력할 부분인데요.
	// c++ 언어의 printf("%ld") 계열 명령어를 이용하면 아주 쉽습니다.
	char *format;
	// 숫자의 범위에 따라 모든 숫자를 몇자리를 출력할 것인지를 정합니다.
	if(num>=1000000000)format="%10ld";
	else if(num>=100000000)format="%9ld";
	else if(num>=10000000)format="%8ld";
	else if(num>=1000000)format="%7ld";
	else if(num>=100000)format="%6ld";
	else if(num>=10000)format="%5ld";
	else if(num>=1000)format="%4ld";
	else if(num>=100)format="%3ld";
	else if(num>=10)format="%2ld";
	else format="%ld ";

	// 줄수만큼 반복
    for (int y = r1; y <= r2; ++y)
    {
		// 칸수만큼 반복하면서
        for (int x = c1; x <= c2; ++x)
        {
			// 맨 첫칸이 아니라면 한칸 띄어 씁니다.
			if(x>c1)printf(" ");
			// 고정길이만큼 숫자를 출력합니다.
            printf(format, map[y-r1][x-c1]);
        }
		// 가로로 한줄 출력이 끝나면 다음 줄로 넘깁니다.
        printf("\n");
    }
              
}
int main()
{
       Result();
	   getchar(); getchar();
       return 0;
}

백준 사이트 도전하실 개발자 분들께 권해드리기는 문제 - 알고리즘 분류 메뉴로 가셔서 자신 있는 분야에서도 윗 줄 부분부터 풀어보시는게 흥미붙이기에 좋습니다.

1000번부터 번호순으로 풀면 갑자기 초반부터 극 난이도 높은 문제가 나와서 곤란하더라구요 ㅎ..