[C] SW Expert Academy 문제풀이 :: 1954번

SW Expert Academy 1954번 달팽이 숫자 문제풀이. 처음에 접근법이 살짝 헷갈렸던 문제. 뭔가 효율적이고 쉬운 방법이 있을 것 같았다. 근데 풀다보니깐 그냥 배열을 만들어 놓고 일일이 메모리에 접근해서 숫자를 대입했다. 컴공 첫 과제로 내는 문제라고들 한다. 몇 번 숫자를 대입하고 방향을 꺾나 세보니 n, n-1, n-1, n-2, n-2, .... 2, 2, 1, 1, 이런 식으로 되더라. 시작부터 n번 오른쪽으로 진행하고 아래로 방향을 꺽고, n-1 아래로 진행하고 왼쪽으로 방향을 꺾는 식. (n, n-1) (n-1, n-2) ,.... (2,1), 1로 분할해줬다.

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE

달팽이는 1부터 N*N까지의 숫자가 시계방향으로 이루어져 있다. 다음과 같이 정수 N을 입력 받아 N크기의 달팽이를 출력하시오.

풀이

#include <stdio.h>
#include <malloc.h>
 
void wayMover(int way[], int *row, int *col) {
    if (way[0] == 1) {
        *col += 1;
    }
    else if (way[1] == 1) {
        *row += 1;
    }
    else if (way[2] == 1) {
        *col -= 1;
    }
    else if (way[3] == 1) {
        *row -= 1;
    }
}
 
void wayTurner(int way[]) {
    if (way[0] == 1) {
        way[0] = 0;
        way[1] = 1;
    }
    else if (way[1] == 1) {
        way[1] = 0;
        way[2] = 1;
    }
    else if (way[2] == 1) {
        way[2] = 0;
        way[3] = 1;
    }
    else if (way[3] == 1) {
        way[3] = 0;
        way[0] = 1;
    }
}
 
int main() {
    int tc;
    scanf("%d", &tc);
 
    for (int t = 0; t < tc; t++) {
        int n;
        scanf("%d", &n);
 
        // 달팽이 공간 할당
        int **snail;
        snail = (int**)malloc(sizeof(int*)*n);
        for (int i = 0; i < n; i++) {
            snail[i] = (int*)malloc(sizeof(int)*n);
        }
 
        // 달팽이 초기화 n*n
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                snail[i][j] = 0;
            }
        }
 
        int num = 0, row = 0, col = -1, cnt = n;
        // right down left up
        int way[4] = { 1,0,0,0 };
 
        for (int k = 0; k < n - 1; k++) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < cnt - i; j++) {
                    wayMover(way, &row, &col);
                    num += 1;
                    snail[row][col] = num;
                }
                wayTurner(way);
            }
            cnt -= 1;
        }
 
        wayMover(way, &row, &col);
        num += 1;
        snail[row][col] = num;
 
        // 달팽이 출력
        printf("#%d\n", t + 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%d ", snail[i][j]);
            }
            printf("\n");
        }
 
        free(snail);
    }
 
    return 0;
}

먼저 wayMover라는 함수를 만들어준다. 주어진 방향에 맞게 한칸씩 이동한다. 파라미터로 주어지는 way[4]에는 순서대로 오른쪽, 아래, 왼쪽, 위의 방향을 의미한다. 1이면 on, 0이면 off다. 즉 오른쪽으로 이동할 때 way[4] = {1,0,0,0}이다. 그리고 각 방향에 맞게 row와 col을 가감해준다. 오른쪽으로 이동한다면 열이 하나씩 증가하는 것이므로 col+=1이다.

wayTurner라는 함수도 만들어준다. 해당 함수가 실행되면 현재 way 배열의 각 값을 확인한 후, 진행 방향을 바꿔준다. 현재 way[4] = {1,0,0,0}이라면 오른쪽을 진행하는 중이므로 아래쪽으로 방향을 틀어줘야 한다. way[4] = {0,1,0,0}이 되어야 하므로 way[0]=0, way[1]=1로 세팅해준다.

n을 입력받아 동적할당으로 nxn 크기의 빈 달팽이 공간을 만들어준다. 그리고 각 칸에 입력할 num=0, 진행 시작 전 값인 row=0, col=-1을 세팅해준다. 일단 한 칸 이동한 다음에 숫자를 입력하는 방식이므로 col=-1부터 시작한다. cnt는 루프를 돌려줄 값이다. n이 5이면 (5,4), (4,3), (3,2), (2,1), 1 순으로 이동하므로 cnt = n부터 시작한다. n, n-1번 루프를 돌리며 숫자를 입력해준 후 cnt 값을 1 깍는다. 그럼 다시 n-1, n-2 루프를 돌리는 식이다.

코드를 줄이기 위해 3중 for문을 썼다. 기본 전개는 n이 3이면 (3,2), (2,1), 1이다. 마지막 1은 마지막에 따로 처리해주는 거고, 괄호 묶음이 2개이므로 n-1번 루프를 돌림을 알 수 있다. 그리고 각 루프에서, 즉 각 괄호 안에서 3과 2를 돌려줘야 한다. 즉 각 i에 대해 cnt-i번 j for문을 돌려준다. j for문은 한 칸 앞으로 가고, num을 하나 증가시키고 현재 위치에 num을 대입하는 것이다. j for문이 끝나면 그 줄의 끝까지 간 것이므로 wayTurner 함수를 사용해서 방향을 꺾는다. 이런 식으로 끝까지 간 후, 마지막 남은 1칸을 위해 한 번 더 앞으로 가고, num을 1 올리고 대입해준다.

그리고 배열을 출력한 뒤 동적할당을 해제하면 끝.