달팽이 알고리즘

오늘은 달팽이 알고리즘을 작성 해보겠다.

절차를 먼저 설명 하자면 

먼저 값을 입력 받는다. 이 후 그 값에 해당하는 결과물이 출력되야한다.

예를 들면

정수 입력 : 3        

      1      2

      0      3

정수 입력 : 15

      1      2      3      4

     12     13     14      5

     11      0     15      6

     10      9      8      7

정수 입력 : 17

      1      2      3      4      5

     16     17      0      0     6

     15      0      0      0      7

     14      0      0      0      8

     13     12     11     10    9

정수 입력 : 35

      1      2      3      4      5         6

     20     21     22     23     24      7

     19     32     33     34     25      8

     18     31      0     35     26       9

     17     30     29     28     27     10

     16     15     14     13     12     11

이런식으로 진행 된다.

그럼 먼저 해당 알고리즘을 적용 하기에 앞서 적절한 2차 배열을 생성 해줘야 한다.

어떠한 규칙이 있는지 살펴 보자

1 / 2 3 4 / 5 6 7 8 9 / 10 11 12 13 14 15 16 /  17 18 ..

/ 를 구분으로 하여 생성되어야 하는 2차배열이 나뉜다.

1 일 때  1x1 배열

2 일 때  2x2 배열

.

.

.

5 일 때 3x3 배열

6

7

8

9

10 일 때 4x4 배열

이 만들어져야 하는것을 볼수 있다.

규칙이 보이나??

이를 어렵게 한번 짜보고 쉽게 한번 짜보자

2.1 어렵게 짜보기 (분기로 짜보자)

1. 2차배열 만들어주기

정사각형의 2차배열의 넓이  즉 해당 인덱스의 제곱이다 그렇다면 한변은 넓이의 제곱근이 되어야 한다.

즉 , 1  4  9  각 각 1  2 3 이 한변의 기리가 되어진다. 그리고 각각 그 사이값들은 더 큰값을 잡아줘야 배열에 채워질 수 있다.

무슨 말이냐면   1  (2,3)  4 에서  2와 3이 채워지려면 1x1이 아닌 2x2 배열이 만들어져야만 채워질수 있다.

이는 사이값들의 제곱근을 구한이후 올림 을 수행 해줘야 한다.

2. 달팽이 알고리즘의 조건식을 위한 규칙

기존의 달팽이 알고리즘들은 2차 배열을 만들어준 후에 한번에 전부 채워 넣는 형식이라 어디까지 넣어야 되는지 고민 할 필요가 없다.

허나 지금 출력값은 받은 입력값에 대하여 어디까지 넣어줘야 하는지를 고려해야 한다.

이러한 조건식을 세워야 하는데 규칙을 알 필요가 있다.

5x5 배열을 예로 들면

이를 보면 대각선을 기점으로 아래는 크고 위에는 값이 더 작아지는것을 볼수 있다

이러한점을 잘 활용 해야 한다. 

또 

      1      2      3      4

     12     13     14     5

     11      0     15     6

     10      9      8      7

을 잘보면 반복성을 찾을 수 있다.

위 그림의 과정을 남은 것이 없을 때 까지 반복 한다는 점이다.

이를 코드로 짜보면

import java.util.InputMismatchException;
import java.util.Scanner;
 
/**
 * <pre>
 * 달팽이 알고리즘 적용
 * </pre>
 * 
 * @author HwangInSung
 * @version 1.0
 * @since 2018.7.11
 */
 
public class SnailAlgorithm {
 
    public static void main(String[] args) {
        String inputNumber;
        System.out.println("달팽이 알고리즘");
        while (true) {
            inputNumber = errVali();
            snailAl(inputNumber);
        }
    }
 
    public static void snailAl(String inputNumber_s) {
        int inputNumber = Integer.parseInt(inputNumber_s);
        int i = 0, j = 0;
        int cnt = 1;
        int side = (int) Math.ceil(Math.sqrt(inputNumber));
        int length=side;
        int[][] snailShell = new int[side][side];
 
        while (true) {
            if (cnt > inputNumber)
                break;
            
            
            // i==j ~ i(side-1)  ->
            if (i == j) {
                for (; j < side; j++) {
                    snailShell[i][j] = cnt++;
                    if (cnt > inputNumber)
                        break;
                }        
                i++;            
            }
            // i(sdie-1) ~ (side-1)(side-1)   
            else if (j -1 == side-1 && i<side) {
                snailShell[i][side-1] = cnt++;
                i++;
                if(i == side) {
                    j-=2;
                    continue;
                }
            } 
            // (side-1)(side-1) ~ (side-1)j
            else if (i-1 == side -1 ) {
                snailShell[side-1][j] = cnt++;
                j--;
                if( ((i-1)+j) < ((length-1)) )
                {
                    i-=2;
                    continue;
                    
                }
            }//(side-1)j ~ ij
            else if ( j+1<i ) {
                snailShell[i][j+1] = cnt++;
                i--;
                if( (j+1) == i) {
                    i++;
                    j=i;
                    side--;
                    
                    continue;
                }
            }
 
        }
        
        for (i = 0; i < length; i++) {
            for (j = 0; j < length; j++) {
                System.out.printf("   %4d",snailShell[i][j]);
            }
            System.out.println();
 
        }
    }
 
    public static String errVali() {
        String inputNumber;
        Scanner sc = new Scanner(System.in);
 
        while (true) {
            try {
                System.out.print("정수 입력 : ");
 
                inputNumber = sc.nextLine();
                // [1] 정수를 입력했는지 오류체크
                if (!UtillClass.isNumber(inputNumber)) {
                    System.out.println("정확한 정수를 입력해주세요");
 
                    continue;
                } // [2] 음수입력하지 않았는지 체크
                else if (Integer.parseInt(inputNumber) < 0)
                    throw new PositiveNumberException("음수 발생");
                else if (Integer.parseInt(inputNumber) == 0) {
                    System.out.println("0");
                }
                break;
 
            } catch (InputMismatchException e) {
                System.out.println("0이상 정수를 입력해주세요");
            } catch (PositiveNumberException e) {
                System.out.println(e.getMessage());
                System.out.println("다시입력 하세요");
            }
 
        }
        return inputNumber;
    }
 
}
 
/*
 * 양수 검증 예외 처리
 * 
 */
 

분기로 짜다 보니 굉장히 난해하고 어렵다.....

하지만 이를 쉽게 짤 수 있다

왜냐하면 달팽이 알고리즘  분기가 필요없고 오로지 진행순서가 직선적이기 때문에 

하나 하나의 과정이 조건에 의해 실행되는것이 아닌 무조건적으로 실행이 된다. 즉 if문을 쓰지 않아도 된다.

2.2 쉽게 짜보기 (직선형 구조)

import java.util.InputMismatchException;
import java.util.Scanner;
 
/**
 * <pre>
 * 달팽이 알고리즘 적용
 * </pre>
 * 
 * @author HwangInSung
 * @version 1.0
 * @since 2018.7.11
 */
 
public class SnailAlgorithm2 {
 
    public static void main(String[] args) {
        String inputNumber;
        System.out.println("달팽이 알고리즘");
        while (true) {
            inputNumber = errVali();
            snailAl(inputNumber);
        }
    }
 
    public static void snailAl(String inputNumber_s) {
        int inputNumber = Integer.parseInt(inputNumber_s);
        int row = 0, col = 0;
        int cnt = 1;
        int side = (int) Math.ceil(Math.sqrt(inputNumber)); // 현재 진행중인 사각형의 길이 , 점점 짧아진다
        int length = side; // 가장 큰 사각형 한변의 길이 ,  고정 된값
        
        int i = 0;
        int[][] snailShell = new int[side][side];  // 정사각형 내용 만큼의 2차배열 만들어주기
 
        Loop1: while (true) {
            if (cnt > inputNumber)
                break;
            for (i = 0; i < side; i++) {
                snailShell[row][col] = cnt++;
                col++;
                if (cnt > inputNumber)
                    break Loop1;
            }
            col--;  // outBoundIndex 되므로 하나 감소
            row++;    // 다음 행부터 진항기 위해 하나 증가
            side--; // 전체 진행 순서가 하나 줄게되므로 1감소
            for (i = 0; i < side; i++) {
                snailShell[row][col] = cnt++;
                row++;
                if (cnt > inputNumber)
                    break Loop1;
            }
            row--;// outBoundIndex 되므로 하나 감소
            col--;// 다음 열부터 진행하기 위한 하나 감소
            for (i = 0; i < side; i++) {
                snailShell[row][col] = cnt++;
                col--;
                if (cnt > inputNumber)
                    break Loop1;
            }
            col++;// outBoundIndex 되므로 하나 증가
            row--; // 다음 행부터 진행하기 위한 하나 감소
            side--; // 전체 순서가 1감소됨
            for (i = 0; i < side; i++) {
                snailShell[row][col] = cnt++;
                row--; 
                if (cnt > inputNumber)
                    break Loop1;
            }
            col++;// outBoundIndex 되므로 하나 증가
            row = col; // 다음 직사각형 index를 넣어주기
 
        }
 
        for (row = 0; row < length; row++) {
            for (col = 0; col < length; col++) {
                System.out.printf("   %4d", snailShell[row][col]);
            }
            System.out.println();
 
        }
    }
 
    public static String errVali() {
        String inputNumber;
        Scanner sc = new Scanner(System.in);
 
        while (true) {
            try {
                System.out.print("정수 입력 : ");
 
                inputNumber = sc.nextLine();
                // [1] 정수를 입력했는지 오류체크
                if (!UtillClass.isNumber(inputNumber)) {
                    System.out.println("정확한 정수를 입력해주세요");
 
                    continue;
                } // [2] 음수입력하지 않았는지 체크
                else if (Integer.parseInt(inputNumber) < 0)
                    throw new PositiveNumberException("음수 발생");
                else if (Integer.parseInt(inputNumber) == 0) {
                    System.out.println("0");
                }
                break;
 
            } catch (InputMismatchException e) {
                System.out.println("0이상 정수를 입력해주세요");
            } catch (PositiveNumberException e) {
                System.out.println(e.getMessage());
                System.out.println("다시입력 하세요");
            }
 
        }
        return inputNumber;
    }
 
}
 
 
 

이에 대한 구조는 이미 구글 검색에 많이 나와있고 나와 크게 다르지 않다

다만 이를 통해 남기고자 하는 말은

 

어떤 알고리즘을 짜기 전에 그 로직이 분기에 의한 것인지 단순 반복작업과 무조건적으로 진행되어지는 것이 먼저 파악 후에

짜보는것이 좋다