https://www.acmicpc.net/problem/1913
1913번: 달팽이
N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서
www.acmicpc.net
난이도: solved.ac 실버 3
구현은 좀 까다로웠지만 아이디어를 생각해내는 건 어렵지 않았다
내 아이디어는 이렇다
먼저 가장 가운데인 1의 위치를 찾아주었는데 이는 쉽게 계산할 수 있다
N을 2로 나눈 몫이 1의 행, 열의 좌표이다 (index가 0부터 시작한다고 할 때)
그리고 r이라는 변수로 반지름을 나타냈는데 이 또한 N을 2로 나눈 몫이다
여기서 반지름이란 맨 가운데인 1부터 맨 바깥 둘레의 거리를 말한다
그리고 각 겹을 level이라는 변수로 나타내었는데 level은 0부터 시작한다
level 0: 1
level 1: 2 ~ 9
level 2: 10 ~ 25
level 3: 26 ~ 49
...
숫자가 이동하는 방향은 아래와 같다
한 level의 맨 마지막 위치로부터 먼저 한 칸 올라가고 오른쪽, 아래, 왼쪽, 윗 방향으로 각 level * 2만큼 이동한다
아래의 그림은 N = 3일 때 달팽이의 모습을 나타내는데
level 0인 1 다음에는 바로 위로 한 칸 올라가고 level 1이 시작된다
그리고 1 * 2칸씩 오른쪽, 아래, 왼쪽, 윗 방향으로 이동한다
N = 5일 때는 아래와 같다
level 1인 9까지를 그렸다면 9에서 바로 위로 한 칸 올라가서 level 2를 시작한다
여기서는 → ↓ ← ↑ 방향으로 4칸씩 이동하는데 이 4는 level 2 * 2를 해서 나온 결과다
이를 코드로 나타내면 아래와 같다
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main() {
int N, num, i, j;
scanf("%d %d", &N, &num);
int** arr = (int**)calloc(N, sizeof(int*));
for (i = 0; i < N; i++)
arr[i] = (int*)calloc(N, sizeof(int));
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int r = N / 2; // 반지름
int x = N / 2, y = N / 2;
int cnt = 1;
arr[x][y] = cnt; // 시작점에 1을 부여
for (int level = 1; level <= r; level++) {
x--; // 한 칸 위로 올려서 시작
for (i = 0; i < 4; i++) {
for (j = 1; j <= level * 2; j++) {
if (i == 0 && j == 1) { // 다음 level로 막 올라가서 한 칸 위로 이동할 때
arr[x][y] = ++cnt;
continue;
}
x += dx[i];
y += dy[i];
arr[x][y] = ++cnt;
}
}
}
int num_x, num_y; // 찾을 숫자의 좌표
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
printf("%d ", arr[i][j]);
if (arr[i][j] == num) {
num_x = i;
num_y = j;
}
}
printf("\n");
}
printf("%d %d", num_x + 1, num_y + 1);
for (i = 0; i < N; i++)
free(arr[i]);
free(arr);
return 0;
}