[자료구조] 배열 연습문제(3): 행렬

[ 문제 1 ] N x N (1≤N≤100) 크기의 행렬에 1 ~ N2의 수를 아래 그림과 같이 차례로 위에서부터 → 방향과 ← 방향을 번갈아 가면서 채운 결과를 출력하시오.

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>

int main(){
    
    int num[101],tmp,N;scanf("%d",&N);
    int right=1,left=0,stt=0,end=N-1;
    for(int i=0;i<(N*N);i++)num[i] = i+1;
   
    for(int k=0;k<N;k++){
        if(right == 1 && left ==0){
            for(int i=stt;i<=end;i++) printf(" %d",num[i]);
            //0부터 4까지
            printf("\n");
            stt = end+N; 
            end ++;
            right = 0;left = 1;
        }
        else if(left == 1 && right == 0){
            for(int i=stt;i>=end;i--) printf(" %d",num[i]);
            printf("\n");
            end  = stt+N;
            stt ++;
            right = 1;left = 0;
        }
    }

    return 0;
}

 

[ 문제 2 ] N x M (1≤N, M≤100) 크기의 행렬에 1 ~ MN 의 수를 아래 그림과 같이 나선형으로 채운 결과를 출력하시오.(달팽이 문제)

#include <stdio.h>

void Arr_print(int arr[100][100],int num_N,int num_M) {
	int num1,num2, turn =1; //turn은 방향 바꾸어주는 변수, num은 반복횟수
	int count = 1; //1부터 n의 제곱까지 나타내주는 변수
	int col = 0, row = -1; //col은 행, row는 열
	num1 = num_N;num2 = num_M;
	while (num1!=0 && num2!=0) {
		for (int i = 0; i < num2; i++) { //행(가로)담당
			row += turn;//열을 증가/감소함
			arr[col][row] += count;//1,2,3,4,,,순으로 저장함
			count++;//count값 업데이트
		}
		num1--; //행/열의 출력이 끝나면 열/행의 반복횟수가 -1이 된다.
		for (int i = 0; i < num1; i++) {//열(세로)담당
			col += turn;//열 증가
			//이때 아까 출력했던 가로부분과 인덱스가 달라야하므로 열을 업데이트하고 값을 저장한다.
			arr[col][row] += count;
			count++;//count값 업데이트
		}
        num2 --; //행/열의 출력이 끝나면 열/행의 반복횟수가 -1이 된다.
		turn *= -1;//방향 전환
	}
	for (int i = 0; i < num_N; i++) {
		for (int j = 0; j < num_M; j++) {
			printf("%3d", arr[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int main(void) {
	int n,m; //n*n배열의 n
	int arr[100][100] = { 0 };
	// printf("숫자를 입력하시오:"); //n의 크기 입력
	scanf("%d %d", &n,&m);// 두 값을 입력받고,
	Arr_print(arr, n,m);//출력 함수를 실행한다.
	return 0;
}

TIP!! 미리 값을 저장하고 출력을 달팽이 모양으로 출력을 하는 것이 아닌 저장 시 달팽이 모양으로 저장하도록 한다.

달팽이 모양으로 배열을 저장하기 위해서는 두 가지가 가장 중요하다.
1. 달팽이 모양으로 배열을 저장하기 위해선 저장 방향이 바뀌는 것에 유의한다. 위 코드는 turn이라는 변수를 이용하여 방향 제어를 했다.
2. 가로/세로를 출력할 때는 다음 세로/가로 출력 시 출력 횟수가 1이 줄어든다. 위 코드에서 num1을 이용한 반복이 끝났을 때 num2가 감소하고 num2를 이용한 반복문이 종료됐을 때 num1이 1이 감소하는 것을 알 수 있다.

(+)Arr_print함수를 보면 입력받은 nun_N, num_M값을 바로 사용하지 않고 다른 변수에 저장하는데, 이는 배열을 출력 시 매개 변수로 사용하기 위함이다.

순서도
main()
1. n,m을 입력받는다.
2. 함수를 실행한다. 이때 인자는 배열과 두 개의 정수형 변수이다.
3. main 함수를 종료한다.

Arr_print()
1. 입력받은 두 정수형 변수를 각각 다른 변수에 저장한다. (입력받은 원래의 값은 배열 출력에 사용한다.)
이때 가로를 저장하는 반복문에서 열을 증가 후 저장하므로 row의 초기값은 -1이어야 한다.
2. num1과 num2가 0이 될 때까지 다음 반복을 실행한다.

(1) num2 (가로길이)만큼 반복하여 count를 저장한다. 이때 열을 turn만큼 증가한다. turn은 가로와 세로의 출력이 끝난 후 *-1을 해주어 값을 업데이트한다. count는 반복할 때마다 +1 한다.
- 열을 증가 후 값을 저장한다. 이전에 저장했던 위치와 중복을 막기 위함이다.
(2) (1)의 (가로의) 출력이 끝나면 세로의 반복 횟수가 -1 된다. 이미 저장한 부분을 제외하기 때문이다.
(3) num1 (세로 길이)만큼 반복하여 count를 저장한다. (1)과 비슷한 방법으로 값을 저장한다.
(4) (3)의 (세로의) 출력이 끝나면 가로의 반복 횟수가 -1 된다. 
(5) turn 변수가 *-1이 된다. 다시 (1)로 돌아가 반복을 시행한다.

[ 문제 5 ] N x M (1≤N, M≤100) 크기의 행렬에 1 ~ MN 의 수를 아래 그림과 같이 ↙ 대각선 방향으로 채운 결과를 출력하시오.

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
int main(){
    int n,m,cnt=1;
    int col=0,row=0,number=0;
    scanf("%d %d",&n,&m);

    int **num = NULL;
    num = (int**)malloc(sizeof(int*)*n);
    for(int i=0;i<n;i++)num[i] = (int*)malloc(sizeof(int)*m);

    while(cnt <= (n*m)){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // printf(">i[%d]+j[%d] = %d\n",i,j,i+j);
                if(number == (i+j)){
                    num[i][j] = cnt;
                    // printf(">num[%d][%d] = %d\n",i,j,num[i][j]);
                    cnt ++;
                    col =i;row = j;
                }
            }
        }
        number ++;
        // if(col == (n-1) && row == (m-1))break;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            printf("%3d",num[i][j]);
        }printf("\n");
    }
}

처음 보면 굉장히 까다로워 보이지만 사고를 조금만 바꿔보면 엄청 쉽게 해결되는 문제이다. 이 문제도 출력을 대각선으로 하는 것이 아닌 저장을 대각선으로 한다는 것이 중요한 포인트이다.

이 문제를 해결하기 위해 인덱스를 활용했는데 같은 대각선 라인의 값들은 행과 열의 합이 같다는 공통점을 가진다. 이러한 규칙을 통해 비교할 number의 값을 2중 반복 문이 끝났을 때 업데이트하고, 최종 값이 (n*m) 보다 작을 때까지 루프를 돌리면 지정된 위치에 값을 저장할 수 있다. 하지만 인덱스의 합이 number와 같도록 비교하는 과정이 비효율적인데, 효율적으로 배열을 정렬하는 법은 모르겠다.

+

문제를 풀기위한 나의 수많은 시도들...