[Python] 백준 1913 달팽이 (구현)

 

📌 문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

 

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

예제 입력 1

7
35

예제 출력 1

49 26 27 28 29 30 31
48 25 10 11 12 13 32
47 24 9 2 3 14 33
46 23 8 1 4 15 34
45 22 7 6 5 16 35
44 21 20 19 18 17 36
43 42 41 40 39 38 37
5 7

 

---

 

📌 풀이

💬 Code

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
snail = [[0]*n for _ in range(n)]

# 가운데 1 채우기
x = (n - 1) // 2
y = (n - 1) // 2
snail[x][y] = 1

# 방향벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

i = 2
start = 3

while x != 0 or y != 0:
    while i <= start * start:
        if x == y == (n - 1) // 2: # 시작점이면 cnt 세팅, 한 칸 위로
            cnt_up, cnt_down, cnt_left, cnt_right = start, start - 1, start - 1, start - 2
            x += dx[0]
            y += dy[0]
            cnt_up -= 1

        elif cnt_right > 0: # 우
            x += dx[3]
            y += dy[3]
            cnt_right -= 1

        elif cnt_down > 0: # 하
            x += dx[1]
            y += dy[1]
            cnt_down -= 1

        elif cnt_left > 0: # 좌
            x += dx[2]
            y += dy[2]
            cnt_left -= 1

        elif cnt_up > 0: # 상
            x += dx[0]
            y += dy[0]
            cnt_up -= 1

        snail[x][y] = i
        i += 1

    n -= 2
    start += 2

for j in range(len(snail)):
    print(*snail[j])
    if m in snail[j]:
        mx = j + 1
        my = snail[j].index(m) + 1
print(mx, my)

💡 Soultion

가운데에서부터 채워나가려고 그려보니 이동 패턴이 항상 같았습니다. 가운데 좌표를 시작점으로 잡고 시작점에서부터 채워나가는 순서에 맞춰 숫자를 저장해주면 됩니다. 시작점은 보이다시피 항상 ((n-1)//2, (n-1)//2)입니다.

 

n = 7일 때를 봅시다.

 

1. 가장 작은 정사각형 채우기 (3x3)
   • n = 7 → 시작점 (3, 3)
   • start = 3
   • n = 3일 때의 가장 작은 정사각형부터 채워야 하므로 start = 3으로 시작합니다. 숫자 i가 start * start인 9가 될 때까지 while문을 반복하며 이동순서대로 이동하면서 배열에 숫자를 채웁니다.
2. 중간 크기 정사각형 채우기 (5x5)
   • n = 5 → 시작점 (2, 2)
   • start = 5
   • n = 5일 때의 정사각형을 채워야 하므로 start = 5로 시작하기 위해 start += 2를 해줍니다. 시작점은 (2, 2)가 되어야 하는데, 시작점 계산 공식이 ((n-1)//2, (n-1)//2)이므로 현재 n값인 7에서 2를 빼주는 n -= 2연산을 수행합니다. 숫자 i가 start * start인 25가 될 때까지 while문을 반복하며 이동순서대로 이동하면서 배열에 숫자를 채웁니다.
3. 가장 큰 정사각형 채우기 (7x7)
   • n = 3 → 시작점 (1, 1)
   • start = 7
   • n = 7일 때의 정사각형을 채워야 하므로 start = 7이 됩니다. 시작점을 구하기 위해 n = 3으로 만들고, 숫자 i가 start * start인 49가 될 때까지 while문을 반복하며 이동순서대로 이동하면서 배열에 숫자를 채웁니다.