백준 1022 회전하는 소용돌이

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

구현을 잘 할수 있는가를 묻는 문제였다.
처음에는 음수인 인덱스가 보기 싫어서 제일 왼쪽으로 밀고 패딩을 주는 방식을 생각했었다.
이 접근의 문제점은 일단 소용돌이의 모든 배열을 저장하려 했다는 생각이다.
소용돌이 최대크기를 모두 저장하는 배열을 선언하려면,
가로 10000 세로 10000 크기의 배열을 선언해야 하는데,
10000 * 10000은 1억으로 381MB의 크기로 메모리 초과가 났다.
그러므로 소용돌이를 돌아가면서 저장해야 하는 인덱스면 정답 배열에 저장을 하였다.

소용돌이를 도는 방법은 시작점부터, 오른쪽 위쪽 왼쪽 아래쪽 오른쪽으로 가면 한 싸이클이 끝난다.
각 싸이클 마다 중점에서 움직일 수 있는 거리가 1씩 증가하고, 이를 패딩의 크기만큼 반복해주면 된다.

배열의 출력에서는 rjust를 이용해 오른쪽 정렬을 하고 빈 공간을 띄어쓰기로 추가하면 된다.

r1,c1,r2,c2 = list(map(int,input().split()))
pad = max(abs(r1),abs(c1),abs(r2),abs(c2))
r1 += pad; c1 += pad; r2 += pad; c2 += pad;

## pad,pad 부터 소용돌이 시작
x,y = pad,pad
cnt = 1
ans = [[0 for i in range(c2-c1+1)] for i in range(r2 - r1 + 1)]
if r1 <= x <= r2 and c1 <= y <= c2:
    ans[x-r1][y-c1] = cnt

dx = [-1,0,1,0] ## 위 오른쪽 아래 왼쪽
dy = [0,1,0,-1]
for k in range(1,pad+1):
    for t in [1,0,3,2,1]:
        while pad - k <= x + dx[t] <= pad + k and pad - k <= y + dy[t] <= pad + k:
            x = x + dx[t]
            y = y + dy[t]
            cnt += 1
            if r1 <= x <= r2 and c1 <= y <= c2:
                ans[x-r1][y-c1] = cnt

m = 0
for i in range(len(ans)):
    for j in range(len(ans[0])):
        m = max(m,ans[i][j])
mstr = str(m)
length = len(mstr)

for i in range(len(ans)):
    for j in range(len(ans[0])):
        tmp = str(ans[i][j])
        print(tmp.rjust(length," "), end = ' ')
    print()