[Python] 달팽이 - 백준

해당 글은 백준 1913번 문제 '달팽이'를 다룬다.

문제

https://www.acmicpc.net/problem/1913

1913번: 달팽이

 

설명

해당 문제는 중앙점(r, c) = (n//2, n//2)에서 시작해서 상좌하우 순으로 이동해가며 표에 숫자를 채워나가면 된다.

5x5 표의 규칙을 찾아보면 중앙점에서 상1 → 좌1 → 하2 → 우2 → 상3 → 좌3 → 하4 → 우4 → 상4(마지막) 로 진행된다.

이때 마지막을 제외하고 방향이 하, 상일때 이동하는 길이가 +1이 되는 것을 볼 수 있다.

이를 이용해서 표를 다 채울 수 있다.

 

코드

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

#상좌하우
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

r = n//2
c = n//2
data[r][c] = 1
len = 1
dir = 0
num = 2
mx, my = r, c

while True:
    for i in range(len):    # 1 1 2 2 3 3 4 4 5
        nx = r + dx[dir]
        ny = c + dy[dir]
        data[nx][ny] = num
        if m == num:        # 숫자 m의 위치 저장
            mx, my = nx, ny
        num += 1
        r, c = nx, ny
        if r == 0 and c == 0:   # 마지막 (0, 0)은 패스하기
            break
    if num > n*n:
        break
    dir = (dir+1)%4
    if dir == 0 or dir == 2:
        len += 1

for i in range(n):
    for j in range(n):
        print(data[i][j], end=' ')
    print()
print(mx+1, my+1)