TIL 달팽이와 방향배열 (22.04.08)

이 글은 과제 제출 기한이 지났고 사이트 내에서 코드도 열람이 가능해졌기 때문에

풀이를 정리해도 될 것 같아 비공개 글에서 공개글로 전환하였습니다.

<안내>
필자도 배우는 입장이라 틀린점, 잘못된 점이 있을 수 있습니다.
그러니 지적, 피드백 환영합니다.

숫자 정사각형 만들기

숫자로 중앙에서부터

0

111
101
111

00000
01110
01010
01110
00000

이런식으로 0과 1이 왔다 갔다하는 도형을 만드는 문제다

풀이까지 가는 과정은 다음과 같다.

일단 100 * 100의 배열을 선언하고 (최대 크기일때도 크기가 넘치지 않는 배열),

그 배열을 0으로 초기화해줘(안에 있는 쓰레기 값을 처리하는 과정)

그러고 시작하는거.그러고 반복문에서 arr[][]을 채우는데, 윗칸, 아랫칸을 색칠할 때는, arr[고정][y--]로 했고,
좌 우를 돌릴땐, arr[y--][고정]으로 만들어서 루프를 돌려보았다.

#include <iostream> // 작동 안되는 코드

using namespace std;

int arr[100][100];

int main() {
    int k, n, x, y, i, j;

    int t;

    cin >> t;

    while(t--) {
        cin >> n; // n 칸 짜리 배열을 만듬 근데 array특성상 빈칸은 일단 모두 0이지.
        k = (n-1)/2;  // k,k 가 중앙이 되도록 일단 짜고 

        for(int i = 0; i<=n;i++)
            for(int j =0;j<=n; j++) arr[i][j] = 0;


        for(x = 0; k >= 2 * x - 1 ; x++){ // 1을 넣는 부분임

            for(y = 2 * x-1 ; y >= -(2 * x-1); y--) { // 0 을 1로 바꿔주는 작업
                arr[k - (2 * x - 1)][k - y] = 1; // 윗칸
                arr[k + (2 * x - 1)][k - y] = 1; // 아래칸
                arr[k - y][k - (2 * x - 1)] = 1; // 왼졲칸
                arr[k - y][k + (2 * x - 1)] = 1; // 오른쪽 
            }    
        }

        for (i = 0; i < n; i++){
            for (j = 0; j < n; j++) {
                cout << arr[i][j];
            }
            cout << "\n";
        }

    }

}

숫자 정사각형 달팽이 모양 출력하기

처음엔 수학적 방법으로 접근했다가 아주 큰 코 다친 문제.

초기에 생각한 방법이다. 수학적 방법으로 어찌되었든 배열이 있으면 모든 부분은 나눌 수 있고,
나눠진 부분은 같은 역할을 하도록 만들면 돌릴 수 있다고 생각했다.

그러나 문제가 발생했다.

마지막 왼쪽 기둥의 진행이 끝나는 순간, 처음 루프로 돌아갔다.

마지막 왼쪽 기둥은 오른쪽으로 진행되어야 했는데,그 과정을 구현하지 않은것이다.

 

#include <iostream> // 작동 안되는 코드
using namespace std;

int arr[1000][1000];
int main() {
    int a, b, i, j, n, x, y, cnt;

    int t;

    cin >> t;


    while(t--) {
        cin >> n >> a >> b;
        cnt = 0; //카운트와 x, y 초기화
        x = 1;
        y = 1;

        while (cnt <= b) {

            if (cnt > a)
                cout << (5*i+j) << " ";

            func(x, y ,n,cnt);

        }
        cout << "\n";

    }
}
int func(int i, int j, int n, int cnt) {
    cnt++;
    if (j >= i && i + j < n) 
        j++; // 함수아닌 버전의 윗줄의 처리에 해당


    else if (j > i && i + j >= n)
        i++; // 함수 아닌 버전의 오른쪽 열 처리에 해당

    else if (j < i && i + j >= n)
        j--; // 함수 아닌 버전 아랫줄 처리에 해당

    else if (j <= i && i + j < n)
        i--; // 함수 아닌 버전 왼쪽 열 처리에 해당

    return cnt;

}

 

이리저리 찾아보고 고민하던 중, 문득 누군가가 말해주었던 방향배열이 생각났다 .

 

방향 배열이란 dx , dy란 배열을 만들어서 제어를 하는 방식이다.

코드를 한번 보도록 하자.

#include <iostream>
using namespace std;

int t, n, a, b;

int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };

int arr[1100][1100];

int main() {
    cin >> t;
    while(t--) {
        cin >> n >> a >> b;

        for(int i = 0; i <= 1010; i++) {
            for(int j = 0; j <= 1010; j++) {
                arr[i][j] = 0;
            }
        }

        int y = 1;
        int x = 1;
        int d = 0;

        for(int i = 1; i <= n * n; i++) {
            arr[y][x] = i;

            if(a <= i && i <= b) cout << (y - 1) * n + x << " ";

            int next_x = x + dx[d];
            int next_y = y + dy[d];

            if(next_x <= 0 || next_x > n || next_y <= 0 || next_y > n || arr[next_y][next_x] != 0) {
                d = (d + 1) % 4;
                next_x = x + dx[d];
                next_y = y + dy[d];
            }

            x = next_x;
            y = next_y;
        }

        cout << "\n";
    }
}

제일 먼저 모든 배열의 내용을 0으로 초기화하고, 달팽이처럼 행렬을 겉에서부터 배열을 채운다.

 

여기서 next_x와 next_y 만드는게 아주 중요한데, next_x는 단순히 x + 1이나 x + i같은 것이 아니라
x + dx[d] 를 해서 d가 바뀌면 계속 변화하도록 만들어준다.

만약 이 배열에서 끝을 만났거나, 이미 도착한 지점을 들어가면, d에 +1을 하고, 방향을 바꾸는 방식.

정말 강력한 방식이다.

 

이전에 오목 문제를 풀면서도 한번 접한 적이 있는 구조였는데, 이번 기회에 내 것으로 만들도록해야겠다.