백준 문제풀이 : (1913) 달팽이 - C/C++

문제 : https://www.acmicpc.net/problem/1913

1913번: 달팽이

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Silver 3	구현

 

 

문제

 

 

풀이

수열을 구성해 출력하는 종류의 문제를 푸는 방법은 일반적으로 두 가지다. 하나는 수열 크기 만큼의 배열을 구성해 각 인덱스에 알맞는 수를 채워넣은 후 배열을 출력하는 것이고, 다른 하나는 수열의 각 인덱스 자리마다의 규칙을 파악해 수열의 앞 숫자부터 계산하여 출력하는 것이다.

 

해당 문제에서도 잘 따져보면 표 안의 숫자들에 규칙성이 있다. 하지만 나는 배열을 만들고 숫자를 채워넣어 배열을 출력하는 방식을 선택했다. 이 경우 입력 수에 따라 배열의 크기도 커져야 하기 때문에 시간 초과와 메모리 초과의 위험이 있지만 다행히 배열 방식의 풀이법으로 무사히 풀렸다.

 

2차원 배열의 크기는 N의 최대값이 999이므로, 999x999로 선언한다. 하지만 배열의 크기가 굉장히 크기 때문에 stack 영역에 선언하면 오류가 발생하게 된다. 따라서 해당 배열은 staic 영역 혹은 heep 영역에 선언해줘야 한다. 나는 vector 자료라이브러리를 사용해 heep 영역에 저장하도록 했다. (Vector 라이브러리는 일반 배열에 비해 접근 속도는 느리지만, 가변 배열에 heep 메모리 영역을 사용하기 때문에 여러모로 유용하다.)

 

이제 N*N 숫자를 시작으로 배열에 차례대로 숫자를 입력하기 시작한다. 하,우,상,좌 순서로, 배열의 모퉁이를 만날 때 마다 방향을 바꾸며 저장할 칸을 옮겨간다. 이 '하, 우, 상, 좌'의 방향을 배열에서의 인덱스의 변화로 표현하면 아래와 같다.

 

하 : x인덱스 감소, y인덱스 유지

우 : x인덱스 유지, y인덱스 증가

상 : x인덱스 감소, y인덱스 유지

좌 : x인덱스 유지, y인덱스 감소 

 

또한, 숫자 저장을 한 바퀴 마칠 때 마다 한 변에서 검사하는 숫자의 개수는 -2 씩 줄어든다. 

그리고 한 바퀴 돌 때마다 검사하는 칸의 개수는 변이 4개이므로, 한 변의 칸 개수*4를 해주면 된다. 

 

이를 코드화하였다.

 

 

코드 작성

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int main() {
    int n, num;
    scanf("%d\n%d", &n, &num);
    
    vector<vector<int>> array(999, vector<int>(999, 0));
    
    int x=0, y=0, number=n*n; //0,0 칸에서 검사 시작. 숫자는 n*n번부터 입력.
    int reX=0, reY=0;
    for (int i=n-1 ; i>0 ; i-=2) {  //한 바퀴 돌때마다 한 변의 칸 개수가 -2됨.
        int count=0;
        for (int j=0 ; j<i*4 ; j++, number--) { // i*4번 칸 검사.  
        	//아래 주석을 합침
            array[x][y] = number; 
            if (number==num) { reX=x; reY=y; } 
            if (count==0) x++; 
            if (count==1) y++;
            if (count==2) x--;
            if (count==3) y--;
        
            if((j+1)%i==0) count++; //i칸번째 마다 방향 바꿈.
        }
        x++; y++;
    }
    
    if (n%2==1) { //n이 홀수면 마지막 중앙 칸에 1이 들어가지 않는다. 해당 사항 보충.
        array[x][y]=1;
        if (num==1) { reX=x; reY=y; }
    }
    
    for (int i=0 ; i<n ; i++) {
        for (int j=0 ; j<n ; j++) {
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
    printf("%d %d", reX+1, reY+1);
}


/*
for (int j=0 ; j<i ; j++, number--) {
    array[x][y] = number;
    x++;
}
for (int j=0 ; j<i ; j++, number--) {
    array[x][y] = number;
    y++;
}
for (int j=0 ; j<i ; j++, number--) {
    array[x][y] = number;
    x--;
}
for (int j=0 ; j<i ; j++, number--) {
    array[x][y] = number;
    y--;
}
*/

 

 

END.