[C++] 달팽이 알고리즘

 

 

정방향 행렬에서 시계 방향으로 탐색 시 N, N-1, N-1, N-2, N-2, ... , 2, 2, 1,1 순서로 값이 채워지는 규칙이 있다. 이 규칙을 이용하면 코드 축약에 도움을 준다. 

 

 

sign 을 사용하는 것은 x가 증가하는 쪽으로 변화하면 다음 y는 감소하는 쪽으로 변화하고, 반대로 y가 증가하면 x는 감소하기 때문이다. 

 

int size=N*N-1, sign=1;
int x=0,y=0;
// 초기 N번 한 번
for(int i(0) ; i<N ; i++){
    pos[0][i]=size--;
    y=i;
}

// N-1 부터 1까지 두 번씩
for(int i(N-1) ; i>0 ; i--){
    for(int j(0) ; j<i ; j++){
        x += sign;
        pos[x][y] = size--;
    }
    sign *= -1;
    for(int j(0) ; j<i ; j++){
        y += sign;
        pos[x][y] = size--;
    }
}

 

출력하면 다음과 같다.