[파이썬 | BOJ | 1022] 소용돌이 예쁘게 출력하기

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

1022번: 소용돌이 예쁘게 출력하기

문제

크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.

 

이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다.

예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.

1. 출력은 r1행부터 r2행까지 차례대로 출력한다.
2. 각 원소는 공백으로 구분한다.
3. 모든 행은 같은 길이를 가져야 한다.
4. 공백의 길이는 최소로 해야 한다.
5. 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
6. 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.

입력

첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다.

출력

r2-r1+1개의 줄에 소용돌이를 예쁘게 출력한다.

 

풀이

알고리즘 분류 : 수학, 구현, 시뮬레이션

 

일단 어떤 좌표 (r, c)가 주어지면, 그 좌표에 해당하는 값을 계산하는것이 주된 알고리즘이다.

어떤 좌표 (r, c)가 있으면, 그 중 절대값이 큰 값이, 껍질 index라고 잡을 수 있다.

 

예를들어 좌표 (-3, 2)이 주어지면 절대값의 max값인 3이 껍질 index가 된다.

 

껍질 index란, 소용돌이 모양으로 숫자를 써 나갈때, 중간 기준으로 n 번째 위치한 한 줄의 사각형 숫자 나열을 뜻한다.

즉, 빨간 사각형이 1번 껍질, 주황 사각형이 2번 껍질, 파란 사각형이 3번 껍질... 이런 식으로 표현 할 수 있다.

 

각 껍질의 모서리에 있는 수를 구할 수 있는데, 맨 오른쪽 아래에 있는 값은, (2 * 껍질 index + 1)^2 이다.

그리고 나머지 모서리도 맨 오른쪽 아래값을 기준으로 일정한 등차수열을 이루므로, 구하는 식을 세울 수 있다.

 

지금까지 구한 모서리값을 기준으로, 어떤 좌표에 해당하는 값을 계산할 수 있다.

 

예를들어 좌표 (-3, 2)이 주어지면, 껍질은 3번이고, 따라서 제일 인접한 모서리인 (-3, 3) 기준으로 한칸 왼쪽값임을 알 수 있다. 다른 예로, 좌표 (1,-2)가 주어지면, 껍질은 2번이고, 가장 인접 모서리인 (2, -2) 기준으로 한칸 위쪽값임을 알 수 있다.

 

위에서 설명한 방법대로 계산하는 알고리즘을 구현하면 다음과 같다.

def selectRegion(r, c):
    if r > 0 and c > 0:
        return 0
    if r > 0 and c <= 0:
        return 1
    if r <= 0 and c <= 0:
        return 2
    if r <=0 and c > 0:
        return 3
 
def cornerVal(n):
    temp = []
    m = (2*n+1)**2
    for i in range(4):
        temp.append(m - 2 * n * i)
    return temp
 
def cal(r, c):
    global maxAns
 
    case = selectRegion(r, c)
    bigger = max(abs(r), abs(c))
    corners = cornerVal(bigger)
 
    if case == 0:
        if abs(r) == bigger:        # (3,2)
            diff = bigger - abs(c)
            ans = corners[0] - diff
        else:                       # (2,3)
            diff = bigger - abs(r)
            ans = corners[3] - (2 * bigger) + diff
 
    elif case == 1:
        if abs(r) == bigger:        # (3,-2)
            diff = bigger - abs(c)
            ans = corners[1] + diff
        else:                       # (2,-3)
            diff = bigger - abs(r)
            ans = corners[1] - diff
 
    elif case == 2:
        if abs(r) == bigger:        # (-3,-2)
            diff = bigger - abs(c)
            ans = corners[2] - diff
        else:                       # (-2,-3)
            diff = bigger - abs(r)
            ans = corners[2] + diff
 
    else:
        if abs(r) == bigger:        # (-3,2)
            diff = bigger - abs(c)
            ans = corners[3] + diff
        else:                       # (-2,3)
            diff = bigger - abs(r)
            ans = corners[3] - diff
    if ans > maxAns:
        maxAns = ans
    return ans

selectRegion 함수로, 가장 인접한 모서리를 찾는 case를 나눠준다.

cornerVal 함수로, 어느 껍질값에 따른 모서리 4개의 값을 계산해서, list로 반환해준다.

cal 함수로, 어떤 좌표 (r, c)에 해당하는, 회오리 값을 찾는다. selectRegion함수에 따른 case에 따라서, 인접 모서리를 찾게되고, 그 모서리로부터 거리차이를 통해서, 좌표의 회오리 값을 계산할 수 있다.

 

 

위 과정을 통해서 어느 좌표 (r, c)에서 회오리 값을 구할 수 있으므로, r1, c1, r2, c2값을 받아서, 이차원 배열(파이썬에서는 리스트안의 리스트)를 만들어서, 배열값에다가 각각의 계산값을 넣어주면된다.

 

이때, 예쁘게 출력해야 하므로, 자리수에 따른 공백을 추가해주어야 하므로, 한번더 2중 for문을 돌리면서, 가장 큰 값보다 자리수가 작은 값들은 공백을 추가해주는 과정을 거친다.

 

최종 코드는 다음과 같다.

 

import sys
read = sys.stdin.readline
maxAns = -1
def selectRegion(r, c):
    if r > 0 and c > 0:
        return 0
    if r > 0 and c <= 0:
        return 1
    if r <= 0 and c <= 0:
        return 2
    if r <=0 and c > 0:
        return 3
 
def cornerVal(n):
    temp = []
    m = (2*n+1)**2
    for i in range(4):
        temp.append(m - 2 * n * i)
    return temp
 
def cal(r, c):
    global maxAns
 
    case = selectRegion(r, c)
    bigger = max(abs(r), abs(c))
    corners = cornerVal(bigger)
 
    if case == 0:
        if abs(r) == bigger:        # (3,2)
            diff = bigger - abs(c)
            ans = corners[0] - diff
        else:                       # (2,3)
            diff = bigger - abs(r)
            ans = corners[3] - (2 * bigger) + diff
 
    elif case == 1:
        if abs(r) == bigger:        # (3,-2)
            diff = bigger - abs(c)
            ans = corners[1] + diff
        else:                       # (2,-3)
            diff = bigger - abs(r)
            ans = corners[1] - diff
 
    elif case == 2:
        if abs(r) == bigger:        # (-3,-2)
            diff = bigger - abs(c)
            ans = corners[2] - diff
        else:                       # (-2,-3)
            diff = bigger - abs(r)
            ans = corners[2] + diff
 
    else:
        if abs(r) == bigger:        # (-3,2)
            diff = bigger - abs(c)
            ans = corners[3] + diff
        else:                       # (-2,3)
            diff = bigger - abs(r)
            ans = corners[3] - diff
    if ans > maxAns:
        maxAns = ans
    return ans
 
r1, c1, r2, c2 = map(int, read().split())
 
R = r2-r1+1
C = c2-c1+1
D = [[0 for _ in range(C)] for _ in range(R)]
 
 
 
for i in range(R):
    for j in range(C):
        D[i][j] = str(cal(r1 + i, c1 + j))
strLen = len(str(maxAns))
 
 
for i in range(R):
    for j in range(C):
        temp = D[i][j]
        D[i][j] = ' ' * (strLen - len(temp))
        D[i][j] += temp
 
for d in D:
    for i in d:
        print(i, end = ' ')
    print()