백준_1022_소용돌이 예쁘게 출력하기

문제

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

풀이

board의 내부의 점 (r, c)가 주어질 때,

board[r][c]에 적어야 할 값을 반환하는 함수 f가 있다고 하자. 

ex)

f(-3, -3) = 37

f(0, 1) =2

1) 어느 그룹에 속하는가?

• 메인그룹

mg = abs(max(r, c, key = abs))

안쪽에서 바깥쪽 껍데기로 나오면서 0, 1, 2... 그룹으로 묶을 수 있다.

0그룹 : 1

1그룹 : 2~9

2그룹 : 10~25 ...

점A (-2, 3)이 주어졌다고 할때 점 A는 3그룹에 속한다. 

• 서브그룹

# corner일때
if abs(r)==abs(c) : 
    if c>0 and r<0 : sg = 0
    elif c<0 and r<0 : sg = 1
    elif c<0 and r>0: sg = 2
    else : sg = 3
# corner가 아닐때
else : 
    if c==mg : sg = 0
    elif -r==mg : sg = 1
    elif -c==mg : sg = 2
    else : sg = 3

ex) 메인그룹3

각 그룹을 다시 4개의 서브그룹으로 나눌 수 있다.

서브그룹1 : 26~31

서브그룹2 : 32~37

서브그룹3 : 38~43

서브그룹4 : 44~49

점A (-2, 3)이 주어졌다고 할때 점 A는 3-1그룹에 속한다. 

2) 어떤 값을 가지는가?

• 모서리를 리스트로 저장

빠른 연산을 위해 서브그룹에서 가장 큰 값(모서리 값)을 리스트에 저장해둔다.

그룹 0에서부터 (사용되는 가장 큰 그룹)까지 모서리값을 미리 구한다. 

gap은 2씩 커지고, main-group에 속하는 원소들은 gap만큼 증가한다.

# main-group 0
corner = [1, 1, 1, 1]
gap = 0
# main-group 1
corner = [3, 5, 7, 9]
gap = 2
# main-group 2
corner = [13, 17, 21, 25]
gap = 4
# main-group 3
corner = [31, 37, 43, 49]
gap = 6

• 모서리에서 얼마나 떨어져 있는가?

점A (-2, 3)은 3-1그룹에 속하고, 가까운 모서리는 B(-3, 3)이다.

점A와 B는 1만큼 떨어져 있으므로, 31보다 1만큼 작은 값을 갖는다.

mg, sg = find_group(i, j)
    closerCorner = pointList[mg][sg]
    dist = distance(i, j, mg, sg)
    number = closerCorner-dist

코드

def find_group(r, c) : 
    mg = abs(max(r, c, key = abs))
    # corner일때
    if abs(r)==abs(c) : 
        if c>0 and r<0 : sg = 0
        elif c<0 and r<0 : sg = 1
        elif c<0 and r>0: sg = 2
        else : sg = 3
    # corner가 아닐때
    else : 
        if c==mg : sg = 0
        elif -r==mg : sg = 1
        elif -c==mg : sg = 2
        else : sg = 3
    
    return mg, sg

def distance(r1, c1, mg, sg) :
    r2, c2 = getPoint(mg, sg)
    return abs(r1-r2)+abs(c1-c2)

def getPoint(mg, sg) : 
    if sg==0 : return -mg, mg
    elif sg==1 : return -mg, -mg
    elif sg==2 : return mg, -mg
    else : return mg, mg

import sys
input = sys.stdin.readline

# 모서리 값 채우기
r1, c1, r2, c2 = map(int, input().strip().split())
gap = 2
pointList = [[1, 1, 1, 1]]
group = abs(max(r1, c1, r2, c2, key = abs))
for _ in range(group) : 
   lastPoint = pointList[-1][-1]+gap
   item = [lastPoint+gap*i for i in range(4)] 
   gap+=2
   pointList.append(item)

# 출력할 값 채우기
maxNum = 0
board = list()
for i in range(r1, r2+1) : 
    line = list()
    for j in range(c1, c2+1) : 
        mg, sg = find_group(i, j)
        closerCorner = pointList[mg][sg]
        dist = distance(i, j, mg, sg)
        line.append(closerCorner-dist)
        maxNum = max(maxNum, closerCorner-dist)
    board.append(line)
    
# 출력하기
length = len(str(maxNum))
ans = list()
for i in range(len(board)):
    for j in range(len(board[0])) : 
        board[i][j] = '{0:-{1}d}'.format(board[i][j], length)
    ans.append(" ".join(board[i]))
ansString = "\n".join(ans)
print(ansString)