[코테] 정수를 나선형으로 배치하기 Lv. 0 (45%)

문제 설명 

양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n^2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

제한사항

1 ≤ n ≤ 30

입출력 예

n	result
4	[[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
5	[[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]]

 

입출력 예 설명

입출력 예 #1

예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.행 \ 열0123

행\열	0	1	2	3
0	1	2	3	4
1	12	13	14	5
2	11	16	15	6
3	10	9	8	7

따라서 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]를 return 합니다.

입출력 예 #2

예제 2번의 n의 값은 5로 5 × 5 배열에 다음과 같이 1부터 25까지 숫자를 채울 수 있습니다.

행 \ 열	0	1	2	3	4
0	1	2	3	4	5
1	16	17	18	19	6
2	15	24	25	20	7
3	14	23	22	21	8
4	13	12	11	10	9

따라서 [[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]]를 return 합니다.

 

문제 이해

• 1부터 n^2까지를 나선형으로 배치해야 하는데 이중 for문으로 구현하면 나선형 순서로 배치하는 각이 안그려지기 때문에 단일 for문을 n^2까지 돌려주도록 합니다.
• 이동 방향이 우 -> 하 -> 좌 -> 상 의 순서가 반복되므로, 이를 지수의 증가,감소로 나타낸 배열을 만들어서 특정 조건에서 이동 방향을 바꾸어 줍니다. (move라는 배열을 생성합니다)
• 이동 방향이 바뀌는 조건으로는 1.n × n 배열을 벗어날때, 2.이미 해당 셀에 값이 존재할 때 입니다.

 

풀이 💡

def solution(n):
    answer = [[None for j in range(n)] for i in range(n)]
    move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    x, y, m = 0, 0, 0
    for i in range(1, n**2 + 1):
        answer[y][x] = i
        if y + move[m][0] >= n or x + move[m][1] >= n or answer[y + move[m][0]][x + move[m][1]]:
            m = (m + 1) % len(move)
        y, x = y + move[m][0], x + move[m][1]
    return answer

 

 

 

 

 

 

 

 

 

우선 answer에 None 값으로 채운 뒤, for문으로 값을 채워주면 if문에서 방문한 지를 판별할 수 있습니다.

answer = [[None for j in range(n)] for i in range(n)]

# n이 5일 경우 answer는
# [[None, None, None, None, None],
# [None, None, None, None, None],
# [None, None, None, None, None],
# [None, None, None, None, None],
# [None, None, None, None, None],]
# 와 같은 빈 배열이 되겠죠

 

방향은 '우, 하, 좌, 상'의 순서이고, 배열의 인덱스를 이동하려면 다음과 같이 증감을 해주어야 합니다.

move = [[0, 1], [1, 0], [0, -1], [-1, 0]]

# [0, 1] 두번째 요소를 증가시키면 '우'로 이동하게 됩니다
# [1, 0] 첫번째 요소를 증가시키면 '하'로 이동하게 됩니다
# [0, -1] 세번째 요소를 감소시키면 '좌'로 이동하게 됩니다
# [-1, 0] 네번째 요소를 감소시키면 '상'로 이동하게 됩니다

이제 조건이 충족될 때 move의 요소를 바꿔 줌으로써 방향을 정할 수 있게 됐습니다.

 

 

[0][0] 부터 n × n 배열을 돌기 시작하므로 좌표를 뜻하는 x, y 값을 0으로 선언하고, move에서 [0, 1]부터 순서대로 사용할 것이기 때문에 m을 0으로 선언해 줍니다. (move[m]은 [0, 1], 즉 '우'로 이동한다는 뜻입니다.)

x, y, m = 0, 0, 0

#x, y는 n x n 배열에서의 좌표를, m은 방향을 의미합니다.

 

for문을 1부터 n**2까지 선회하기 위해서는 range(1, n**2 + 1)로 해주어야 합니다. range는 (이상, 미만)이므로 두번째 파라미터는 포함되지 않습니다.

for i in range(1, n**2 + 1):	# i = 1 ~ n^2

 

i값을 먼저  입력을 해주고 다음 입력할 값의 방향을 정해주어야 합니다.

 

answer[y][x] = i	# y는 행, x는 열

 

 

y는 move의 요소 배열에서 첫번째 요소와 더해주고, x는 두번째 요소와 더해서 이동을 합니다.

# 이동 방향을 바꿔주는 특정 조건식
if y + move[m][0] >= n or x + move[m][1] >= n or answer[y + move[m][0]][x + move[m][1]]:

# 예를 들어, m이 0일 경우 move[m]이 [0, 1]이 되어 y+0, x+1 즉, '우'로 이동하게 됩니다.

3개의 조건이 있는데 앞의 두 조건은 x,y와 이동할 방향의 합이 n보다 클 때이고 이때 n x n 배열의 밖으로 벗어났으니 방향을 바꿔준다는 의미입니다.

마지막 조건은 저도 공부하면서 놀란 부분인데, 자바스크립트에 익숙해져서 '이게 어떻게 실행이 되지?' 라고 생각이 들었습니다.

n보다 크게 벗어나는 경우는 정했으니, 0보다 작게 벗어나는 경우도 조건에 넣어야겠죠?

3 x 3 배열을 예로 들어보겠습니다.

# n = 3
answer = 
[[1,2,3],
 [8,9,4],
 [7,6,5]]
 # i = 7일 경우, 방향을 바꾸어 주지 않으면 i = 8에서 왼쪽 밖으로 벗어납니다

i = 8에서 [2][-1]이 되는데 자바스크립트와 달리 파이썬에서는 가장 뒤에있는 요소가 선택됩니다.

오른쪽부터 시작했으니 오른쪽 값은 무조건 존재하므로 세번째 조건에 포함되어 방향이 바뀝니다.

또한 그 이후로는 이미 방문한 셀일 경우, 세번째 조건에 포함되어 방향이 바뀝니다.

 

 

move배열은 0,1,2,3 네 개의 요소에서 반복되므로, 1을 증가시켜 주면서 4로 나눠서 4보다 커지는 것을 방지합니다

m = (m + 1) % len(move)		# len(move)는 4 고정이므로, len(move)대신 4로 써도 무방합니다

 

바뀐 방향을 적용한 다음 셀의 좌표를 설정합니다.

y, x = y + move[m][0], x + move[m][1]

 

for문을 완료한 배열 answer를 반환합니다.

 

 

나의 풀이 💡

def solution(n):
    direction = 0
    row = 0
    col = 0
    answer = list(list(0 for i in range(n)) for j in range(n))
    copy = list(list(False for i in range(n)) for j in range(n))
    
    
    for i in range(n**2):
        answer[row][col] = i + 1
        copy[row][col] = True
        if direction % 4 == 0:
            # 우
            if 0<=col+1<n and not copy[row][col+1]:
                col += 1
            else:
                direction += 1            
                row += 1

        elif direction % 4 == 1:
            # 하
            if 0<=row+1<n and not copy[row+1][col]:
                row += 1
            else:
                direction += 1
                col -= 1

        elif direction % 4 == 2:
            # 좌
            if 0<=col-1<n and not copy[row][col-1]:
                col -= 1
            else:
                direction += 1
                row -= 1

        elif direction % 4 == 3:
            # 상
            if 0<=row-1<n and not copy[row-1][col]:
                row -= 1
            else:
                direction += 1
                col += 1
    return answer

 

저는 방향 배열을 따로 설정하지 않고, direction에 따라 row를 이동할 지, col을 이동할지 조건을 주었습니다.

copy 배열은 answer배열의 방문 여부를 위한 복사본인데, 첫 풀이를 보니 없어도 될 것 같네요.

 

direction 값에 따라 row, col이 다르게 이동하기 때문에 4개로 나누었습니다.

 

move 배열의 존재하나 차이로 훨씬 간단하게 해결되는 문제였습니다.

1 ~ n^2까지 순회하면서 방향을 바꿔준다는 로직은 두 풀이가 동일하네요.

 

더 좋은 풀이법이나 궁금한 점이 있으시면 댓글 부탁드립니다. 감사합니다.