(C++) 나선형 행렬 채우기

1. 문제

n X m 배열의 [0, 0] 셀에서 출발하여 1부터 nm 사이의 정수를 “나선형” 순서로 채우는

알고리즘 spiral(n, m)을 작성하라.

 

전제: 1 ≤ n, m ≤ 100

실행예: n, m 값을 입력받아 spiral 알고리즘을 이용하여 초기화된 배열을 출력하는 프로그램을 작성하라

예: 4 X 5 배열 A

2. 풀이

나선형은 네가지로 나눌 수 있다. 

또한 나선형은 반복되며 나선원의 반경이 점점 작아진다. 

• 왼쪽->오른쪽

왼쪽에서 오른쪽으로 x축으로 index가 증가한다. 

y축은 항상 가장 높은 곳으로 고정이다.

• 위 -> 아래

위쪽에서 아래쪽으로 y축으로 index가 증가한다. 

x축은 항상 가장 오른쪽으로 고정이다.

• 오른쪽 -> 왼쪽

오른쪽에서 왼쪽으로 x축으로 index가 감소한다. 

y축은 항상 가장 낮은 곳으로 고정이다.

• 아래 ->위

아래쪽에서 위쪽으로 y축으로 index가 감소한다. 

x축은 항상 가장 왼쪽으로 고정이다.

 

이렇게 한 사이클이 돌고나면, loop 가 안쪽으로 이동하며

top = top +1;

bottom = bottom -1;

left = left +1;

right = right -1;

로 이동한다.

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

int n;
int m;

int main(){
	vector <vector <int >>spiralArr;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		vector <int> element(m);
		spiralArr.push_back(element);
	}

	int left = 0;
	int right = m-1;
	int top = 0;
	int bottom = n-1;

	int index = 1;
	while (left <= right && top<= bottom) {
		for (int j = left; j < right; j++) {
			spiralArr[top][j] = index;
			index++;
		}

		for (int i = top; i < bottom; i++) {
			spiralArr[i][right] = index;
			index++;
		}

		for (int j = right; j > left; j--) {
			spiralArr[bottom][j] = index;
			index++;
		}

		for (int i = bottom; i > top; i--) {
			spiralArr[i][left] = index;
			index++;
		}
		left = left + 1;
		right = right - 1;
		top = top + 1;
		bottom = bottom - 1;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << spiralArr[i][j];
		}
		cout << "\n";
	}

	return 0;
}

4. 그외

간단하게 생겨서 금방 풀줄 알았는데 은근 까다로웠다

그래도 카카오 풀다가 이거푸니까 뇌가 숨쉬는 것 같다^^7

알고리즘 수업 레포트가 나온다던데  레포트 내용도 블로그에 정리하면 좋을둡...ㅎㅎ