[알고리즘] 달팽이 수열

 달팽이 수열이란 그림과 같이 2차원 배열의 숫자들이달팽이의 껍질처럼오름차순으로 빙글빙글 채워지는 규칙을띄고 있습니다.

MapleStory 초록달팽이 펌ㅋ

규칙을 파악하는 것은 어렵지 않았지만, 코드로 구현할 때는 해결방법이 쉽게 떠오르지 않아 상당한 시간을 들였던 기억이 납니다. DFS를 사용할 수도 있지만, 이 글에서는 무한 루프와 for 문 2개를 가지고 해결해보려 합니다.

 

그런데 정답을 알아보기 전에, 여러분은 어떠한 규칙을 발견할 수 있으셨나요? 

 

1. 1을 시작으로 값이 1씩 증가한다.
2. 오른쪽으로 갔다, 아래로 갔다 왼쪽으로 갔다, 위로 갔다. 가 반복된다.

와 같은 규칙을 어렵지 않게 발견할 수 있었을 겁니다.

 

여기서 1번을 구현하기 위해서는 num 이라는 변수를 1로 초기화해서 num++; 로 하나씩 증가시키면 될 것 같아 보입니다.

하지만, 2번은 음... 고민을 좀 많이 해야할 것 같아요.

 

2번 규칙을 구현하기 위해서는 다음 사진을 이해할 필요가 있습니다.

제가 서두에 무한루프(while(true)) 1개와 for 문 2개를 사용한다고 했었죠?

그림의 사각형은 여러분이 채워나갈 2차원 배열이라고 생각하시면 됩니다.

화살표는 숫자가 채워질 방향이에요~ 그리고 화살표가 어떤 건 색칠되어 있고

어떤 건 비어있는데, 그 이유는 나중에 코드를 통해 봐야 정확히 알 수 있겠지만,

배열의 인덱스 가 증감하는 방향이 바뀌기 때문이라고 우선 말씀을 드리고 시작할게요~

그리고 그림을 유심히 살펴보면, 빨강색 왼쪽 대각선을 기준으로 왼쪽과 오른쪽의 명암이 다른 것을 알 수 있는데.

이 사실을 기억하고 코드를 살펴봅시다!

 

            int n = 3;
            int arr[][] = new int[n][n];

            int dir = 1;
            int len = n;
            int num = 1;
            int i = 0;
            int j = -1;

            while(true)
            {
                // 1. 가로로 len만큼 이동
                for (int p = 0; p < len; p++) // p는 len만큼 나아간다.
                {
                    j += dir;
                    arr[i][j] = num++;
                }
                // 횟수 줄이고 더이상 진행할 수 없으면 탈출
                if(--len == 0) break;
                // 2. 세로로 이동
                for (int p = 0; p < len; p++)
                {
                    i += dir;
                    arr[i][j] = num++;
                }
                // dir 부호 바꾸기
                dir *= -1;
            }

다 읽어 보셨나요? 변수들에 대해 설명해드리겠습니다.

• n: 배열의 가로 세로 길이에요
• arr[][]: 숫자를 담을 배열이에요
• dir: 위에서 강조한 배열의 인덱스 가 증감하는 방향이에요~
  • 1이면 인덱스가 증가하고, -1이면 인덱스가 감소할 거예요!
• len: 각 화살표에서 얼마만큼 이동을 할 것인지를 나타내는 길이에요
• num: 이 친구를 계속 1씩 증가시켜 수열을 만들거예요
• i와 j: 각각 숫자가 들어갈 행과 열의 인덱스를 가리키게 할 거예요.
  • 그런데 j는 왜 -1부터 시작할까요?? 
• 반복문 안의 p: 길이 len 만큼 이동하게 하려고 만든 친구예요.

 

그리고나서 반복문을 크게 3조각으로 나눠보죠!

1. 가로로 이동하는 부분
2. 이동길이를 감소하고 종료조건을 검사하는 부분
3. 세로로 이동하는 부분

 

그리고 1번과 3번은 컴퓨터적으로 다음과 같은 의미가 있습니다.

1. 가로 이동: 

• =>: 열을 나타내는 인덱스 j가 하나씩 증가해야한다.
• <=: 열을 나타내는 인덱스 j가 하나씩 감소해야한다.

3. 세로 이동:

• ^ : 행을 나타내는 인덱스 i가 하나씩 감소해야한다.
• v  : 행을 나타내는 인덱스 i가 하나씩 증가해야한다.

 

그리고 1번과 3번은 합치면 맨 처음에는 ㄱ 자 모양으로 숫자가 채워질 것입니다.

(j가 -1부터 시작한 이유는 맨처음 dir 이 j에 더해지면서 0으로 초기화 되면 0,0부터 채워지지 않고 1,0부터 채워져버리기 때문이예요!)

 

그런데 while 문의 마지막을 보면 dir 에 -1을 곱하는 연산이 들어가 있습니다.

따라서 다음 while 문에서 dir이 -1이 되어 i와 j의 인덱스가 감소해나가는 것을 알 수 있게됩니다.

그러면 ㄴ 자 모양으로 이제 숫자가 채워지겠죠?

 

자 그러면 이 규칙을 적용하면 달팽이 모양으로 숫자가 채워지는 것을 예상할 수 있어요!

 

그런데, 서두에서 저희는 가장바깥에 무한루프를 둔다고 했었죠? 종료조건을 줘서 탈출을 시킬 필요가 있습니다.

그 때는 언제일까요? 네 진행 길이를 나타내는 len 의 값이 0이 되어 더이상 숫자를 증가시킬 수 없게 되었을 때입니다.

 

if(--len == 0 ) break; 문장을 통해 길이가 0이 되면 더이상 진행할 수 없다고 판단되어 while 문을 탈출하고 달팽이 수열

을 완성시킬 수 있습니다.

 

이와 관련된 문제를 다음 사이트에서 연습하실 수 있으니 관심이 있으신 분들은 참고하시면 도움이 될 것 같습니다.

질문이나 오탈자에 대한 지적은 언제나 환영합니다. 감사합니다. ^^

 

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq&