[자료구조] 배열에 대각선으로 숫자 채우기

자료구조 배열 대각선으로 숫자 채우기

이 포스트는 지난 포스트인 달팽이 배열에 이어지는 내용입니다. 참고해주세요

man-25-1.tistory.com/72

[자료구조] 달팽이 배열(배열에 나선형으로 숫자 채우기)

지난번에는 N x M 배열에 나선형으로 숫자를 채우는 문제를 풀어봤는데 이번 포스트에서는 대각선으로 숫자를 채우는 문제를 다뤄보겠습니다.

문제는 N x M 배열을 입력받고, 1부터 N xM 숫자까지 배열에 대각선으로 순차적으로 숫자를 채워넣어서 출력하는 문제입니다. 

 

접근

달팽이 배열과 마찬가지로 처음 접근 아이디어를, 배열에 0을 채우고 0을 없애나가는 과정으로 접근했습니다.

알고리즘을 생각해보면 단순합니다. start 지점에서 출발하여 우측으로 가면서 대각선으로 숫자를 채우고, 우측으로 더 이상 갈수 없게되면 아래로 내려가면서 대각선으로 숫자를 채웁니다. 즉 쉽게 생각하면, 보드판 위의 말이 다음 그림처럼 이동하게 되고 각 지점에서 대각선으로 움직이고 다음 지점으로 이동하는 과정을 반복하면 됩니다.

 

풀이

지금까지 정리한 내용을 구현해보게 되면

1. 보드판위의 말은 start지점부터 end지점까지 이동해야한다. ( => 큰 반복의 종료조건)

 1-1. start지점에서 모서리 지점까지 오른쪽으로 이동하는 구간

 1-2 모서리 지점에서 end지점까지 아래쪽으로 이동하는 구간

 

2. 각 지점에서는 왼쪽 아래 대각선으로 배열의 끝을 만날때까지 이동해야한다. 즉 인덱스상으로 행은 1 증가하고, 열은 1감소하는 형태로 구현하게 된다. ( ==> 대각선 이동의 구현)

 

따라서 1-1의 구간에서 대각선이동을 구현하고, 1-2의 구간에서 대각선 이동을 구현합니다.

 

1-1 구간의 대각선 이동이 실행되고 난 뒤의 모습은 다음과 같습니다.

1-2 구간의 대각선 이동이 실행되면 다음과 같습니다

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#pragma warning(disable:4996) #include <stdio.h> int arr[100][100]; int main() {     int N, M;     scanf("%d %d", &N, &M);     int row = N, col = M;     int i = 0, j = 0;     int a = 1;       //0으로 초기화해서 게임판 만들기     for (i = 0; i < row; i++) {         for (j = 0; j < col; j++) {             arr[i][j] = 0;         }     }     //start포인트 설정     int point_i = 0;     int point_j = 0;     arr[point_i][point_j] = 1;     a = 1;     //0 잡아먹기 게임시작           while (point_j + 1 < M && arr[point_i][point_j + 1] == 0) {             point_j++;//우측 이동             a++;             //대각선 작업 행은 +,열은 -             i = point_i;             j = point_j;             arr[i][j] = a;             while(i + 1 < N&&j-1>=0 && arr[i+1][j-1]==0){             a++;             arr[i+1][j-1] = a;             i++;             j--;             }         }                while (point_i + 1 < N && arr[point_i + 1][point_j] == 0) {             point_i++;// 아래로 이동             a++;             //대각선 작업 행은 +,열은 -             i = point_i;             j = point_j;             arr[i][j] = a;               while (i+1<N&&j - 1 >= 0 && arr[i + 1][j - 1] == 0) {                 a++;                 arr[i + 1][j - 1] = a;                 i++;                 j--;             }         }                     //출력     for (i = 0; i < row; i++) {         for (j = 0; j < col; j++) {             printf(" %2d", arr[i][j]);           }         printf("\n");     } } Colored by Color Scripter

cs