파이썬으로 달팽이 수열 만들기
파이썬으로 알고리즘 시뮬레이션을 공부하던 중 가장 기본이 되는 문제를 소개하려고 합니다.
처음에는 잘 이해가 가지 않았지만 열심히 이해해 보기 위해서 정리한 글 입니다.
문제 이해하기
달팽이 수열은 1부터 시작하여 시계방향으로 증가하는 수를 배열에 담는 방법으로 처음에는 오른쪽으로 이동하며 수를 채우고, 그 다음은 아래쪽으로 이동하며 수를 채우고, 다시 왼쪽으로 이동하며 수를 채웁니다. 그리고 다시 위쪽으로 이동하며 수를 채우는 과정을 반복합니다.
예를 들어 간단한 달팽이 수열을 만들어 보면 아래와 같습니다. 달팽이 모양처럼 숫자가 늘어나고 있는 것을 확인하실 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 3 x 3
1 2 3
8 9 4
7 6 5
# 4 x 4
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
그러면 이제부터 본격적으로 이것을 어떻게 구현해야 하는지 알아보겠습니다.
첫 번째 배열 초기화 하기
우리가 크기가 n인 달팽이 배열을 받는다고 했을 때 가장 첫 번째로 해야하는 일은 nxn의 배열을 생성한 후 초기화 해야 합니다. 여기서는 n = 3인 배열을 예로 들겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(n):
snail_array = [[0] * n for _ in range(n)]
# 초기화 된 배열
# [
# [0,0,0]
# [0,0,0]
# [0,0,0]
# ]
solution(3)
시작숫자와 행 열 인덱스 초기화 하기
그리고 달팽이 수열의 시작숫자인 1을 설정 하고 행과 열의 시작과 끝 인덱스를 설정합니다. 행과 열의 시작과 끝 인덱스는 방향전환을 하며 숫자를 채워나갈 수 있게 해줄 수 있는 숫자 입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(n):
snail_array = [[0] * n for _ in range(n)]
# 달팽이 수열의 시작 숫자
start_num = 1
# 행과 열의 시작과 끝 인덱스
start_row, end_row = 0, n-1
start_col, end_col = 0, n-1
solution(3)
반복문 조건 설정하기
이제 시뮬레이션을 시작할 반복문을 구현합니다. 반복문의 조건은 while 문으로 행과 열의 시작인덱스와 끝 인덱스의 사이에 있는 값일 경우에만 반복이 동작하도록 해야 합니다.
각각의 값이 끝 값을 초과 한다면 배열이 다 채워졌다는 것을 의미합니다.
1
2
3
4
5
6
7
8
9
def solution(n):
# ... 배열 초기화
# ... 달팽이 열의 시작숫자
# ... 행과 열의 시작과 끝 인덱스
while start_row <= end_row and star_col <= end_col:
첫 번째 행 삽입하기
첫 번째 행을 삽입하는 과정은 아주 쉽습니다. 현재 n이 3이므로 배열의 [0][0] ~ [0][2] 인덱스까지 증가된 번호를 삽입 시키고 첫 번째 열이 증가했으므로 start_row의 값을 하나 증가시켜 줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(n):
# ... 배열 초기화
# ... 달팽이 열의 시작숫자
# ... 행과 열의 시작과 끝 인덱스
while start_row <= end_row and star_col <= end_col:
# 첫 번째 행 채우기
for i in range(start_col, end_col + 1):
snail_array[start_row][i] = start_num
start_num += 1
start_row +=1
# 결과는 1 2 3
마지막 열 삽입하기
배열은 시계방향으로 삽입되므로 이제는 마지막 열을 삽입해야 합니다. 마지막 열은 이전에 삽입 했었던 start_row 의 인덱스 부터 시작하여 [0][2] [1][2] 자리에 증가된 start_num 인 4와 5를 삽입하게 됩니다.
그리고 가장 마지막 열은 삽입 되었으므로 end_col을 하나 감소시킵니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(n):
# ... 배열 초기화
# ... 달팽이 열의 시작숫자
# ... 행과 열의 시작과 끝 인덱스
while start_row <= end_row and star_col <= end_col:
# .. 첫 번째 행 채우기
# 마지막 열 채우기
for i in range(start_row, end_row + 1):
snail_array[i][end_col] = start_num
start_num += 1
end_col -=1
# 결과는 1 2 3
# 4
# 5
마지막 행 삽입하기
이제 세 번째로 마지막 행을 삽입해야 합니다. 행의 시작인덱스와 마지막 인덱스를 확인합니다. 마지막 행의 가장 왼쪽 부분인 5가 채워져 있으므로 여기서는 end_col 부터 start_col - 1 까지 반대로 시작해야 합니다.
그리고 end_row값은 현재 2 이기 때문에 [2][1] [2][0]에 증가된 값을 삽입하게 됩니다. 이후 마찬가지로 마지막 행을 삽입했으므로 end_row 값을 하나 감소시켜 줘야 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n):
# ... 배열 초기화
# ... 달팽이 열의 시작숫자
# ... 행과 열의 시작과 끝 인덱스
while start_row <= end_row and star_col <= end_col:
# .. 첫 번째 행 채우기
# .. 마지막 열 채우기
# 마지막 행 채우기
if start_row <= end_row:
for i in range(end_col, start_col - 1, -1):
snail_array[end_row][i] = start_num
start_num += 1
end_row -= 1
# 결과는 1 2 3
# 4
# 7 6 5
첫 번째 열 삽입하기
이제 마지막 단계로 첫 번째 열을 삽입해야 합니다. 현재 첫 번째 열은 start_row = 1가 한나 증가했고 end_row = 1로 하나 감소한 상태 때문에 8이 하나 들어가야 합니다.
따라서 8이 들어갈 자리는 현재의 start_col값과 row의 값인 [0][1]에 삽입 되게 됩니다.
그리고 시작열을 마쳤으므로 start_col이 증가시켜줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(n):
# ... 배열 초기화
# ... 달팽이 열의 시작숫자
# ... 행과 열의 시작과 끝 인덱스
while start_row <= end_row and star_col <= end_col:
# .. 첫 번째 행 채우기
# .. 마지막 열 채우기
# .. 마지막 행 채우기
# .. 첫 번째 열 채우기
if start_col <= end_col:
for i in range(end_row, start_row - 1, -1):
snail_array[i][start_col] = start_num
start_num += 1
start_col += 1
# 결과는 1 2 3
# 8 4
# 7 6 5
전체 구현 코드
이 과정을 while 반복문이 조건이 끝날때 까지 반복하면 결과가 완료됩니다. 전체 코드는 아래와 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def solution(n):
snail_array = [[0] * n for _ in range(n)]
# 달팽이 수열의 시작 숫자
start_num = 1
# 행과 열의 시작과 끝 인덱스
start_row, end_row = 0, n-1
start_col, end_col = 0, n-1
while start_row <= end_row and start_col <= end_col:
# 첫 번째 행 채우기
for i in range(start_col, end_col + 1):
snail_array[start_row][i] = start_num
start_num += 1
start_row +=1
# 결과는 1 2 3
# 마지막 열 채우기
for i in range(start_row, end_row + 1):
snail_array[i][end_col] = start_num
start_num+=1
end_col-=1
# 결과는 1 2 3
# 4
# 5
# 마지막 행 채우기
if start_row <= end_row:
for i in range(end_col, start_col-1, -1):
snail_array[end_row][i] = start_num
start_num+=1
end_row-=1
# 결과는 1 2 3
# 4
# 7 6 5
# 첫 번째 열 채우기
if start_col <= end_col:
for i in range(end_row, start_row-1, -1):
snail_array[i][start_col] = start_num
start_num+=1
start_col+=1
# 결과는 1 2 3
# 8 4
# 7 6 5
# 결과 출력
for el in snail_array:
print(el)
solution(3)