[백준 알고리즘] 1913번 달팽이 (C++)

문제 정의

문제의 핵심은 홀수인 자연수 N이 주어지면, 1부터 $N^2$까지의 자연수를 아래와 같이 달팽이 모양으로 $N * N$의 표에 채우라는 것이다.

 

입력

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

 

출력

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

 

 

접근 방법

알고리즘을 처음 접하는 입장으로써 주위 개발자에게 조언을 구했다. 처음엔 코드를 작성하면서 변수를 생각했다. 하지만 이것은 비효율적인 방법이라고 한다. 머리로 사용할 변수들을 최대한 미리 생각하고 이후에 필요에 따라 추가/제거 하는 것이 중요하다. 

 

1. 먼저 문제에서 바로 확인할 수 있는 변수 두 개인 홀수 자연수를 N으로 두고, 찾아야 할 값을 want로 선언하였다.

 

2. 찾아야 할 값 want의 2차원 좌표를 나타낼 변수를 x, y로 선언하였다.

 

3. 2차원 배열을 다루기 위해 사용되는 행렬을 row, col로 선언하였다.

 

4. 그리고 핵심이 되는 것은 dir(direction)이라는 방향을 나타내는 변수이다.

 

dir은 위와 같은 흐름으로 2차원 배열 변수에 값을 담기 위한 변수이다. dir을 1 또는 -1로 설정하여 row와 col에 더해줄 것이다. dir을 1로 설정하여 row에 더해줄 경우 자연스럽게 row가 증가하고, col에 더해줄 경우 col이 증가한다. 이후 dir을 -1로 설정하면 row가 감소하고, col이 감소한다. 이후 다시 dir을 1로 설정하면 row가 증가하여 최종적으로 1에 도달하는 식이다. (위 그림에 맞대어 row와 col에 dir을 더해주는 것을 시뮬레이션 해볼 것을 권한다. 이것이 문제 풀이의 핵심이다)

 

작성 코드

#include <iostream>
#include <cstring>

using namespace std;

int main(void)
{
	// 1. 변수 선언부
	int N = 0; // 입력 받을 홀수 자연수
	int want = 0; // N^2 이하의 찾고자 하는 자연수
	int x = 0, y = 0 ; // Want의 좌표를 나타낼 x, y 값
	int row = -1, col = 0;; // 달팽이를 나타낼 행, 열
	int dir = 1; // 방향을 나타낼 변수
	cin >> N;
	int copy = N;
	cin >> want;
	int squared = N * N; // N^2을 표현할 변수

	int** arr;
	arr = new int* [N]; // 2차원 배열의에서 사용할 배열의 길이(row)

	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N]; // N = 2차원 배열에서 사용할 배열의 길이(column)
		memset(arr[i], 0, sizeof(int)*N); // 0으로 배열 초기화 for security.
	}


	// 2. 핵심 알고리즘 동작부
	while (squared > 0)
	{
		for (int i = 0; i < copy; i++)
		{
			row = row + dir;
			arr[row][col] = squared;
			if (squared == want)
			{
				x = row + 1;
				y = col + 1;
			}
			squared = squared - 1;
		}

		copy = copy - 1;
		for (int i = 0; i < copy; i++)
		{
			col = col + dir;
			arr[row][col] = squared;
			if (squared == want)
			{
				x = row + 1;
				y = col + 1;
			}
			squared = squared - 1;
		}
		dir = dir * (-1);
	}

	// 3. 결과 출력부
	for (int i = 0; i < N * N; i++)
	{
		int r = i / N;
		int c = i % N;
		cout << arr[r][c] << " ";
		if ((i % N) == N - 1) cout << endl;
	}

	cout << x << " " << y << endl;


	// 4. 2차원 배열 할당 해제부
	for (int i = 0; i < N; i++)
		delete[] arr[i];
	delete[] arr;

	return 0;
}

 

코드는 크게 4개의 부로 구성된다.

 

1. 변수 선언부

알고리즘 작성 이전에 필요로 하는 변수를 선언한 부분이다.

 

2. 핵심 알고리즘 동작부

배열에 값을 넣기 위한 핵심적인 알고리즘이 동작하는 부분이다.

 

3. 결과 출력부

$N^2$부터 1까지 달팽이 모양으로 출력하는 부분이다.

 

4. 2차원 배열 할당 해제부

달팽이 모양으로 값을 담기 위해 생성했던 2차원 동적 배열을 할당 해제하는 부분이다.

 

 

참고로 memset 함수는 0, -1로만 초기화 가능하다. 그 이유는 바이트 단위로 초기화가 이루어지기 때문이다.

 

정답 비율 & 제출 결과

 

 

초반에 알고리즘 풀지 못했을 때 정답 비율이 50%나 된다는 것에 가벼운 충격을 받았다. 최소한 둘에 하나는 풀 수 있다는 생각에 말이다. 아무튼 동시에 초심자로서 알고리즘적 사고를 잘 하는 사람들이 많다는 것에 내게 자극을 심어준 문제였다.

 

Reference

[1] https://walewalu.tistory.com/4