[Codeup] 1476. 2차원 배열 빗금 채우기 3-1

1. 문제 설명

다음과 같은 n*m 배열 구조를 출력해보자.

입력이 3 4인 경우 다음과 같이 출력한다.
1 3 6 9
2 5 8 11
4 7 10 12

입력이 4 5인 경우는 다음과 같이 출력한다.
1 3 6 10 14
2 5 9 13 17
4 8 12 16 19
7 11 15 18 20

입력이 n m인 경우의 2차원 배열을 출력해보자.

 

2. 문제 풀이

2차원 배열을 순회하면서 빗금을 치듯 채우는 문제이다.

배열 채우기 문제들이 대부분 그렇듯, 그냥 순회만 잘하면 풀리는 문제이다.

2-1. 아이디어

일반적인 배열 채우기 문제는 보통 가로나 세로처럼 일직선 방향으로 이동하면서 값을 채운다.

하지만, 이 문제는 대각선 단위로 채워야 한다.

 

위는 예제로 사용한 3x4 배열이다. 같은 대각선 위에 있는 칸들은 같은 색으로 표기했다.

이때, 같은 대각선에 있는 칸들은 좌표의 합이 같다는 특징이 있다.

 

순회의 순서는 대각선 상 가장 왼쪽 아래 칸부터 시작해 오른쪽 위 방향으로 진행한다.

따라서, 오른쪽 위로 순회를 하더라도 다음 대각선을 시작하기 위한 시작점은 따로 기억해 두어야 한다.

 

2-2. 구현 (C++ Source Code)

구현시 가장 중요한 점은 현재 대각선의 시작점을 별도로 기억해 두는 것이다.

대각선을 따라 오른쪽 위로 이동하는 동안에는 시작점을 건드리지 않고,

대각선 순회가 모두 끝난 뒤에만 다음 시작점으로 갱신해야 한다.

#include <iostream>
using namespace std;
int main(void)
{
	int n, m;
	int cnt = 1;
	int start_i = 1, start_j = 1;
	int data[105][105] = { 0 };

	cin >> n >> m;
	while (cnt <= n * m)
	{
		int i = start_i;
		int j = start_j;

		while (i >= 1 && j <= m) // 대각선 범위를 벗어나기 전까지 계속 감. 
		{
			data[i][j] = cnt;
			cnt++;

			i--;
			j++;

		}
        
		start_i++; // 빗금 시작점 갱신
		if (start_i == n + 1) // 범위를 넘은 경우 오른쪽으로 이동
		{
			start_i = n;
			start_j++;
		}
		
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cout << data[i][j] << " ";
		}
		cout << endl;
	}
}