[코드트리 챌린지] 가운데에서 시작하여 빙빙 돌기

[문제]

https://www.codetree.ai/cote/13/problems/snail-start-from-center?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

가운데부터 시작해서 1,1, 2,2, 4,4 식으로 커지면서 끝까지 가게 만들는 배열을 만드는 문제이다.

 

사실 딱 1년전 백준에 똑같이 있는 문제인 달팽이 문제를 풀었는데 당시에는 위, 아래, 우측, 좌측 가는 함수를 모두 만들고 숫자를 모두 세면서 가운데에서 직접 이동하게 만들었다.

 

하지만, 지금 와서 생각해보니 굳이 가운데에서 시작을 하지 말고 출구가 되는 가장 마지막에서 시작해서 거꾸로 가는것이 더 쉽게 문제를 구할 수 있다는것을 깨달았다.

 

고로, 우리는 n-1,n-1부터 시작해서 가운데로 이어지게끔 서쪽 -> 북쪽 -> 동쪽 -> 남쪽 순으로 이동을 하게 만들것이다.

그렇기에 idx를 n * n 으로 두고 차례대로 가면서 1이 될때 바로 빠져나올수 있게 반복문을 짜자.

[회고]

.

[코드]

#include <iostream>

using namespace std;

int n;
int arr[101][101];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < n){
        return true;
    }
    return false;
}

int main() {
    cin>>n;
    arr[n-1][n-1] = n * n;
    int dict = 2;
    int idx = n * n;
    int x = n -1;
    int y = n - 1;

    //1, 1 ,2, 2, 4, 4, 
    for(;idx > 1;){
        int nextX = x + dx[dict];
        int nextY = y + dy[dict];
        if(inRange(nextX,nextY) == false || arr[nextX][nextY] != 0){
            dict = (dict - 1 + 4) % 4;
            continue;
        }
        x = nextX;
        y = nextY;
        idx--;
        arr[x][y] = idx;
    }

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