[백준] 1913번 - 달팽이 / C++

문제

홀수인 자연수 N(3≤N≤999)이 주어지면, 다음과 같이 1부터 N^2까지의 자연수를 달팽이 모양으로 N*N의 표에 늘어놓을 수 있다.

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N^2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

 

입력

첫째 줄에 홀수인 자연수 N이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N^2 이하의 자연수가 하나 주어진다.

 

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

 

코드

#include <iostream>

using namespace std;

int N;
int target;
int board[1000][1000];
int pos[2];

void make_board()
{
	int r, c, dir = 0;		// 좌표와 진행 방향
	int l, limit = 1;		// 현재 방향으로 이동할 횟수
	int num = 1;			// 1 ~ N^2
	int dr[] = {-1, 0, 1, 0};	// 반시계방향으로 이동 (U-R-D-L)
	int dc[] = {0, 1, 0, -1};

	// 시작 좌표 (= 중심 좌표)
	r = (N + 1) / 2;
	c = (N + 1) / 2;
	// 1 ~ N^2 저장
	while (num <= N * N)
	{
		for (l = 0; l < limit; l++)
		{
			// 좌표을 알고 싶은 숫자라면 좌표를 저장
			if (num == target)
			{
				pos[0] = r;
				pos[1] = c;
			}
			// 표에 숫자를 저장
			board[r][c] = num++;
			// 다음 좌표로 이동
			r += dr[dir];
			c += dc[dir];
		}
		// 다음 방향으로 회전
		if (++dir == 4)
			dir = 0;
		// 방향이 위/아래이면 이동할 횟수를 1만큼 증가
		if (dir % 2 == 0)
			limit++;
	}
}

void print_board()
{
	int i, j;

	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
			cout << board[i][j] << " ";
		cout << endl;
	}
	cout << pos[0] << " " << pos[1] << endl;
}

int main()
{
	cin >> N >> target;
	make_board();
	print_board();
	return 0;
}

 

표의 중심 좌표에서 시작해 반시계 방향으로 숫자를 저장한다. 입력되는 N은 홀수이므로 항상 중심 좌표는 존재한다. 표의 좌표는 (1, 1)부터 (N, N)까지이고, 이때 중심 좌표는 (N + 1) / 2로 구할 수 있다. 진행 방향은 위쪽부터 오른쪽, 아래쪽, 왼쪽 순서로 반복된다. 배열 dr과 dc는 진행 방향에 따라 다음 좌표를 계산하기 위한 값을 저장한다. 다음은 N이 5인 경우의 표이다.

숫자가 저장되는 순서를 보면 다음과 같은 규칙을 가지는 것을 알 수 있다. 방향이 두 번 바뀔 때마다 해당 행 또는 열에 저장하는 숫자의 수가 늘어난다. 이 규칙을 적용하기 위해 바뀐 방향이 위 또는 아래인 경우 방향을 바꾸기 전까지 저장할 숫자의 수를 늘려준다.

규칙대로라면 마지막에 5개의 숫자를 저장해야 하지만 N^2까지의 숫자만 저장되기 때문에 5번째 수 (N^2 + 1)은 저장되지 않는다.

 

링크

1913번: 달팽이

inbdni/Baekjoon