[코드트리 챌린지] 빙빙 돌며 숫자 사각형 채우기 2

[문제]

https://www.codetree.ai/cote/13/problems/snail-number-square-2?&utm_source=clipboard&utm_medium=text 

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

[문제 풀이]

백준 달팽이와 비슷한 문제이다.

(0,0)부터 시작해서 밑으로갔다 우측으로 갔다 위로 갔다 좌측으로 가면서 계속해서 가운데를 향해 가면서 n * m 배열을 꽉 채우는 문제이다.

사실 해당 문제를 풀기 전에 코드 트리 개념쪽에서 n * n 배열을 풀었기에 어렵지 않았던 것이 크다.

 

반복문을 돌리면서 다음에 올 x값과 y값이 범위를 벗어났거나 이미 방문을 했다면 방향을 바꿔주고 그렇지 않다면 계속해서 돌게 만들어주자.

코드 트리 정해는 딱 n * m 을 for문으로 돌려서 풀었지만 나중에 방향실수 같은게 있을 만한 부분인것 같애서 for문은 n * m 이 다 채워질때까지 돌리게 만들었다.

자세한 부분은 코드를 보면 이해가 쉬울 것이다.

 

[회고]

찾아보니 지금으로부터 딱 1년전에 풀었던 문제인데 달팽이 문제 참 어렵게 접근을 했었다.

당시 실력이 나쁜 수준은 아니었던것 같은데 시뮬레이션 문제들에 쓰이는 기술이 있는것과 없는것이 문제 푸는 시간 단축에 차이가 많이 생기는것 같다.

[코드]

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int arr[101][101];

//북 동 남 서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

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

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

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

    return 0;
}