[Baekjoon/백준][1913][C/C++] 달팽이

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

2차원 배열 문제 중에 가장 풀어보고 싶었던 문제. 처음 코딩 배울 때 이 문제를 봤었는데, 그때 못 풀어보고 이제야 생각나서 풀어본다.

1. 문제

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

1913번: 달팽이

[문제]

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

9	2	3
8	1	4
7	6	5

 

25	10	11	12	13
24	9	2	3	14
23	8	1	4	15
22	7	6	5	16
21	20	19	18	17

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

[입력]

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

[출력]

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

[예제 입력 1]

7
35

[예제 출력 1]

49 26 27 28 29 30 31
48 25 10 11 12 13 32
47 24 9 2 3 14 33
46 23 8 1 4 15 34
45 22 7 6 5 16 35
44 21 20 19 18 17 36
43 42 41 40 39 38 37
5 7

2. 풀이

코드 순서대로 풀이를 해보겠다.

 

[n, key값 입력 받음]

N은 입력으로 주어지는 자연수.

key는 위치를 찾고자 하는 자연수.

 

[2차원 동적 배열 할당]

C에서는 2차원 동적 배열 할당을 위해 반복문을 이용한다. 기본 형태는 아래 코드에서 나타나는 것과 같다.

(여기서 약간의 변형을 거치면, 동적 할당을 해제하기 좀 더 편리하게 만들 수도 있다. 하단 링크 참조.)

https://codeng.tistory.com/8

[c언어] 2차원 배열 동적 할당하기

[달팽이 채워 넣기]

오늘 코딩의 핵심 부분.

 

변수를 선언하고 초기화 한 값부터 살펴보자. 처음 배열 인덱스의 시작점은 배열의 중심이므로, 세로값에 해당하는 col과, 가로값에 해당하는 row에, 각각 N/2값을 대입한다. num값은 배열 안에 입력될 숫자이다. (1, 2, 3, ... $N^2$까지 증가한다.) 

 

달팽이의 원리를 살펴보면, '①배열에 값을 입력한다. -> ②배열 인덱스 위치를 변경한다.' 이 2가지 행위의 반복이다. '①배열에 값을 입력한다.' 부분은 별로 어려울 게 없지만, '②배열 인덱스 위치를 변경한다.' 파트가 머리 아프다. 인덱스 위치를 변경하기 위해서는 '②-⑴위,오른쪽,아래,왼쪽 방향 중 하나로 ②-⑵1칸,  2칸, 3칸, ... 중 상황에 맞게 해당 칸수를 이동한다.' 를 구현해야 한다. 

 

U=Up, R=Right, D=Down, L=Left라 하자. 달팽이의 이동 방향 원리를 살펴보면, U - R - D - D - L - L - U - U - U - R - R - R - D - D -D -D - ... 해서 U가 1번, R이 1번, D가 2번, L이 2번, U가 3번, R이 3번, D가 4번, ... 순서대로 진행됨을 알 수 있다. ∴ URDL 순서대로 U1번, R1번, D2번, L2번, U3번, R3번, D4번, L4번, ... 씩 이동하게 설계하면 된다. (같은 숫자를 2번 반복하기 위해서, 2번째 for문의 (URDL + 1) / 2 를 이용했다.)

 

이후 하단의 for문 2개를 잘 맞물리게 설계해 주면, 잘 작동된다. (사실 이 부분은 말로 자세히 설명하기가 어렵다...ㅠ)

 

[출력_달팽이] & [출력_Key의 위치]

문제의 요구사항에 맞게 값을 출력하는 과정이다.

 

[마무리]

동적 배열을 사용했으므로, 마지막에는 반드시 동적 할당을 해제해주어야 한다.

3. 코드

#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
	/* N, key값 입력 받음 */
	int N; scanf("%d", &N);
	int key; scanf("%d", &key);

	/* 2차원 동적배열 할당 */
	int** arr = (int**)calloc(N, sizeof(int*));
	for (int i = 0; i < N; i++)
		arr[i] = (int*)calloc(N, sizeof(int));

	/* 달팽이 채워넣기 */
	int col = N / 2;
	int row = N / 2;
	int num = 1;

	for (int URDL = 1; num <= N * N; URDL++) { //URDL은 Up Right Down Left를 의미
		for (int i = 1; i <= (URDL + 1) / 2; i++) {
			/* part1. 쓰기 */
			arr[col][row] = num++;

			/* part2. 위치 */
			/* UP */
			if (URDL % 4 == 1)
				col--;
			/* RIGHT */
			else if (URDL % 4 == 2)
				row++;
			/* DOWN */
			else if (URDL % 4 == 3)
				col++;
			/* LEFT */
			else if (URDL % 4 == 0)
				row--;
		}
	}

	/* 출력_달팽이 */
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf("%d ", arr[i][j]);
		printf("\n");
	}

	/* 출력_key값 위치 */
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (key == arr[i][j])
				printf("%d %d", i + 1, j + 1);
		
	/* 마무리 */
	for (int i = 0; i < N; i++)
		free(arr[i]);
	free(arr);

	return 0;
}