BOJ 1913 : 달팽이

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1913

 

 

배열의 중심 좌표에서 달팽이 모양의 배열을 만들면 된다.

 

먼저 배열의 중심 좌표 (sr, sc)는 N / 2 + 1이 된다.

문제의 예시 7인 경우 (4, 4) 부터 배열이 시작됨을 알 수 있다.

sr = sc = N / 2 + 1;

 

N = 5인 경우 규칙을 살펴보자.

먼저 처음 1 → 2의 방향은 ↑ 방향이 된다.

달팽이는 ↑, →, ↓, ← 로 방향을 반복해서 바꾼다.

따라서, dr, dc는 아래와 같이 정의할 수 있다.

/* ↑, →, ↓, ← */
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

 

방향이 두 번 바뀔 때 마다, 움직이는 칸이 1칸씩 늘어난다. 실제 방향을 표시해보면

 

↑, →, ↓, ↓, ←, ←, ↑, ↑, ↑, →, →, →, ... 

 

이 된다.

그리고 방향을 2 * N - 1번 바꾸게 된다. 

따라서 아래와 같이 구현할 수 있다.

index = 1;
snail[sr][sc] = index++;
for (int i = 0; i < 2 * N - 1; i++)
{
	/* 방향이 2번 바뀔 때 마다 움직이는 칸 수 증가 */
	if (i % 2 == 0) size++;

	/* 방향을 보고 움직이기 */
	for (int s = 0; s < size; s++)
	{
		...
	}

	/* 방향이 4가 되는 경우 다시 원위치 */
	dir++;
	if (dir == 4) dir = 0;
}

size는 해당 방향에 대해 움직여야 하는 칸수가 된다.

 

dr, dc 배열을 보고 index를 계속 증가시키면서 snail 2차원 배열에 저장하면 완성이다.

그리고 입력값(M)이 index와 일치하면 좌표를 저장하고 배열과 함께 출력하면 된다.

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (1000 + 100)

int N, M;
int snail[MAX][MAX];

void output(int map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
}

/* ↑, →, ↓, ← */
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

void makeSnail()
{
	int ansr, ansc;
	int sr, sc, dir, index, size;

	ansr = ansc = N / 2 + 1; /* 초기화 */
	dir = index = size = 0;
	sr = sc = N / 2 + 1;

	index = 1;
	snail[sr][sc] = index++;
	for (int i = 0; i < 2 * N - 1; i++)
	{
		/* 방향이 2번 바뀔 때 마다 움직이는 칸 수 증가 */
		if (i % 2 == 0) size++;

		/* 방향을 보고 움직이기 */
		for (int s = 0; s < size; s++)
		{
			int nr, nc;

			nr = sr + dr[dir];
			nc = sc + dc[dir];

			/* index가 M인 경우 좌표 저장 */
			if (index == M)
			{
				ansr = nr;
				ansc = nc;
			}

			snail[nr][nc] = index++;

			sr = nr;
			sc = nc;
		}

		/* 방향이 4가 되는 경우 다시 원위치 */
		dir++;
		if (dir == 4) dir = 0;
	}

	output(snail);
	printf("%d %d\n", ansr, ansc);
}

int main()
{
	scanf("%d %d", &N, &M);

	makeSnail();

	return 0;
}