알고리즘 문제풀이(Java) - 달팽이문제(2차원배열)

 

달팽이 문제란 

 

1   2   3   4  5 

16 17 18 19  6

15 24 25 20  7

14 23 22 21  8

13 12 11 10  9

 

와 같이 숫자가 시계방향으로 돌아가면서 바깥부터 안쪽으로 채워지는 형태의 2차원 배열을 구현하는것을 의미한다.

 

숫자는 어차피 1씩 증가하면서 배열에 저장되므로 중점을 두고 보아야 할 부분은 '배열의 index'이다. 

 

편의상 배열의 index는 arr[i][j]로 한다.

 

달팽이 문제는 크게 다음과 같은 두가지 관점으로 볼 수 있다.

• 가로(width)부분은 j값의 증감
• 세로(length)부분은 i값의 증감

 

1set를 시작지점에서 가로 혹은 세로의 끝 지점까지 간다고 볼 때 각 set는 다음과 같다.

• 0~5까지를 보면 arr[0][0], arr[0][1] , arr[0][2], arr[0][3], arr[0][4]에 각각의 값이 저장되었다.
  • 1set에서는 i는 가만히 있고 j가 1씩 증가했다.
• 6~9까지를 보면 arr[1][4], arr[2][4], arr[3][4], arr[4][4]에 각각의 값이 저장되었다.
  • 2set에서는 j가 가만히 있고 i가 1씩 증가했다.
• 10~13까지를 보면 arr[4][3], arr[4][2], arr[4][1], arr[4][0]에 각각의 값이 저장되었다.
  • 3set에서는 i는 가만히 있고 j가 1씩 감소했다.
• 14~16까지를 보면 arr[3][0], arr[2][0], arr[1][0]에 각각의 값이 저장되었다.
  • 4set에서는 i가 1씩 감소하고 j는 가만히 있었다.

 

결론

 

1~4set의 규칙이 계속해서 반복되며 숫자가 채워진다. 

•  j가 끝까지 증가 -> i가 끝까지 증가 -> j가 끝까지 감소 -> i가 끝까지 감소 

 

여기서 끝까지라는 말은 값이 채워지지 않은 부분까지를 말한다. 

 

끝까지 간다고 해서 이미 '1'이 들어있는 arr[0][0]에 다른 값이 들어올 수는 없다.

 

while loop로 전체를 감싸는 반복문을 만들고 그 안에 1~4set을 구성하는 각각의 for loop을 구성한다.

 

 

 

 

소스코드

 

import java.util.Scanner;
   public class TwoDimArray_Spiral{
	   public static void main(String[] args){
		   int size = 0;
		   Scanner sc = new Scanner(System.in);
		   System.out.println("배열의 크기를 입력하세요");
           size = sc.nextInt();
           int [][] arr = new int[size][size];
           int num = 1; // 배열에 들어갈 첫번째 숫자
           int count = size*size; // 마지막 숫자
           int i = 0; int j = 0;
           int width = size;
           int length = size-1;
           while(num<=count){
               for(int k=0; k<width; k++){
                   arr[i][j] = num;
                   j++; num++;
               }width--; i++; j--;

               for(int k=0; k<length; k++){
                    arr[i][j] = num;
                    i++; num++;
               }length--; i--; j--;

               for(int k=0; k<width; k++){
                   arr[i][j] = num;
                   j--; num++;
               }width--; i--; j++;

               for(int k=0; k<length; k++){
                    arr[i][j] = num;
                    i--; num++;
               }length--; i++; j++;               
           }
	   }
       for(int i=0; i<arr.length; i++){
           for(int j=0; j<arr[i].length; j++){
               System.out.printf("%3d", arr[i][j]);
           }
           System.out.println()
       }
   }