[Algo] zigzag scanning

인덱스 접근 배열 선언

#include <iostream>

using namespace std;

int main() {
	int zag_idx[8 * 8] = { 0,1,8,16,9,2,3,10,17,24,32,25,18,11,4,5,12,19,26,33,40,48,41,34,27,20,13,6,7,14,21,28,35,42,49,56,57,50,43,36,29,22,15,23,30,37,44,51,58,59,52,45,38,31,39,46,53,60,61,54,47,55,62,63 };
	int board[8][8];

	int val = 0;
	for (int i = 0; i < 8 * 8; i++) {
		int cy = zag_idx[i] / 8;
		int cx = zag_idx[i] % 8;

		board[cy][cx] = val++;
	}

	for (int y = 0; y < 8; y++) {
		for (int x = 0; x < 8; x++) {
			printf("%3d", board[y][x]);
		}
		printf("\n");
	}

	return 0;
}

구현

PS 풀 듯이 단순히 구현하여 풀기

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;

	vector<vector<int>> board(n, vector<int>(n));


	int cy = 0;
	int cx = 0;
	int dir = -1; // -1: 아래로, 1: 위로
	int val = 0;
	board[0][0] = val++;
	while (!(cy == n - 1 && cx == n - 1)) {
		if (cx == n - 1) {
			cy++;
		}
		else if (cy == n - 1) {
			cx++;
		}
		else if (cy == 0) {
			cx++;
		}
		else if (cx == 0) {
			cy++;
		}
		

		while (cy >= 0 && cx >= 0 && cy < n && cx < n) {
			board[cy][cx] = val++;

			cy = cy - dir;
			cx = cx + dir;
		}

		cy = cy + dir;
		cx = cx - dir;
		dir = -dir;
	}


	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			printf("%3d ", board[y][x]);
		}
		printf("\n");
	}
	printf("\n");

	return 0;
}

수학적으로 풀기

유도과정

위의 사진을 보면 알 수 있듯이, zigzag로 시작되는 부분만 때서 보면 삼각수 순열과 똑같이 진행된다.

$T(n)$ 에서 $n$에 해당하는 부분이 뭘까?
zigzag 행렬에서 $(x , y)$의 합이 각 대각선마다 일치하며, $x+y$는 $T(n)$에 해당하는 $n$이다.

$x+y = n$이었으므로 정리하자면 이렇다

$x = k - T(n)$
$y=n-x$

---

zigzag scanning은 우상향/좌하향으로 진행되는데,
$n$이 짝수라면 우상향이고
$n$이 홀수라면 좌하향이다

그리고 scaning 방식이 절반을 기준으로 대칭으로 진행되기 때문에 반대편과 같이 채워줄 수 있다.

코드

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {
	int n;
	cin >> n;

	vector<vector<int>> board(n, vector<int>(n));
	for (int k = 0; k <= n * n / 2; k++) {
		int T = (sqrt(8 * k + 1) - 1) / 2;
		int y = k - ((T * (T + 1)) / 2);

		if (T & 1) {
			board[y][T - y] = k;
			board[(n - 1) - y][(n - 1) - (T - y)] = (n * n) - 1 - k;
		}
		else {
			board[T - y][y] = k;
			board[(n - 1) - (T - y)][(n - 1) - y] = (n * n) - 1 - k;
		}
	}

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			printf("%3d ", board[y][x]);
		}
		printf("\n");
	}
	printf("\n");

	return 0;
}