[Python] BOJ(백준) 1022 소용돌이 예쁘게 출력하기

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

 

백준 문제 중 '시도했지만 맞지 못한 문제' 도장 깨기를 해보려고 한다.

구현 문제다.

중앙부터 시작해 돌아 나오는 소용돌이 중 (r1, c1) 부터 (r2, c2)를 출력하면 되는 문제다.

 

소용돌이 최대 크기가 10001 x 10001 이라서 그냥 만들어 놓고 범위만 출력하면 안되나? 했는데 어림도 없다.

열심히 규칙을 찾기 위해 이리 저리 숫자 놀이를 해본 결과 8이라는 숫자를 이용할 수 있었다.

1을 중심으로 8방향으로 점점 커지는 숫자들의 규칙이 (공차가) 8씩 증가했다.

위로 가는 걸 기준으로 1 4 15 34 --- 이 숫자들이 간격은 3 11 13 --- 간격의 간격이 모두 8이었다.

8방향 모두 같은 규칙이고, 간격의 시작점만 달랐다.

그래서 (0, 0) 1을 중심으로 8등분을 해서 그 좌표마다 계산해야 하나... 했는데 도저히 그림이 나오지 않았다...

 

갖가지 방법을 정말 많이 생각해봤는데 8등분이라는 틀에 갖혀 빠져나오질 못했다.

시작점의 값만 찾아내서 주변을 점차 넓혀 가며 모든 값을 찾아내려 했다.

(r1, c1)의 위치가 어디냐에 따라서 경우의 수가 너무 많아졌다...

이틀을 고민 했는데 8등분, 첫 점 찾기에서 빠져나오질 못했다.

 

GPT에게 힌트만 요청한 결과 틀을 깨고 나와 문제를 해결할 수 있었다.

 

각 위치마다 수식으로 계산하라는 점에서 깨달을 수 있었다.

정말 어이가 없게도 숫자들의 간격의 간격이 8이라는 건 알아냈지만

좌측 상단부터 바라봤던 지라 우측 하단이 (2n + 1) ^ 2라는 것을 몰랐었다.

이렇게 힌트들을 얻어 문제를 해결했다.

 

우리가 흔히 사용하는 배열과 다르게 좌표처럼 중간이 (0, 0)인 점,

그래서 배열 위치에 음수와 양수가 모두 쓰인다는 점을 이용해서 k번째 껍질의 최댓값은 쉽게 구할 수 있었다.

거기서 꼅질의 사각형 중 어떤 변인지에 따라 계산을 해줬다.

 

이 부분도 4등분, 8등분 생각에 깨닫는 데 좀 걸렸다. (예시로 계산 하는 것도 첫번째 껍질로 해서 0, 1, -1 만 나와서 고생했다...)

n번째 껍질인 경우 아랫 변은 행이 n, 윗 변은 행이 -n, 왼쪽 변은 열이 -n, 오른쪽 변은 열이 n이다.

한 줄의 끝과 끝은 2n 만큼 차이가 난다. 아래는 해당 부분 코드다.

if i == k2:	# 아래
    k -= (k2 - j)
elif j == -k2:	# 왼쪽
    k -= (2 * k2)
    k -= (k2 - i)
elif i == -k2:	# 위
    k -= (4 * k2)
    k -= (k2 + j)
else:		# 오른쪽
    k -= (6 * k2)
    k -= (k2 + i)

 

그리고 이 문제는 예쁘게 출력하기 이므로 출력의 공백도 중요하다.

파이썬을 이용해서 문제를 풀었기 때문에 몇자리 수인지 확인하기 위해서 간단하게 문자열로 변환해 길이를 측정했다.

첫 열은 앞에 공백이 없어야 한다는 생각에 또 시행착오를 겪었지만...

출력 면에서는 큰 문제가 없이 해결했다.

 

for i in range(len(arr)):
    for j in range(len(arr[0])):
        cnt = len(str(arr[i][j]))
        print(" " * (msize - cnt), end = '')
        print(arr[i][j], end = " ")
    print()

 

import sys

input = sys.stdin.readline
n1, m1, n2, m2 = map(int, input().split())

arr = []
m = 0
for i in range(n1, n2 + 1):
    lst = []
    for j in range(m1, m2 + 1):
        k2 = max(abs(i), abs(j))
        k = (2 * k2 + 1) ** 2
        
        if i == k2:
            k -= (k2 - j)
        elif j == -k2:
            k -= (2 * k2)
            k -= (k2 - i)
        elif i == -k2:
            k -= (4 * k2)
            k -= (k2 + j)
        else:
            k -= (6 * k2)
            k -= (k2 + i)

        m = max(m, k)
        lst.append(k)

    arr.append(lst)

msize = len(str(m))

for i in range(len(arr)):
    for j in range(len(arr[0])):
        cnt = len(str(arr[i][j]))
        print(" " * (msize - cnt), end = '')
        print(arr[i][j], end = " ")
    print()

 

옛날에는 풀다가 모르겠으면 질문 게시판을 열심히 뒤적거리거나, 포기하고 인터넷에 있는 코드들을 참고 했었다.

진짜 약간의 힌트만 얻고 싶어도 방법이 없었는데 세상이 좋아져서 GPT가 다 도와준다...

힌트를 받긴 했지만 열심히 고민하고 해결해서 또 다르게 뿌듯하다.