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

알고리즘 문제풀이

목록 보기

112/113

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

아이디어

1. 제약조건 관찰

소용돌이의 크기는 최대 1만 $\times$ 1만 = 1억이다. int 데이터가 4바이트임을 고려하면, 1부터 일일이 값을 구하는 것은 어려울 것 같다. 그러므로 규칙성을 찾아, 특정 칸의 좌표에 따라 소용돌이 값을 바로 찾을 수 있는 소용돌이 함수 f(y, x)를 만들 것이다.

2. 변수 매개화

소용돌이의 모양을 자세히 보면, 두 가지 사실을 관찰해볼 수 있다.

한 바퀴를 돌 때마다 나무의 나이테처럼 중심으로부터 거리가 늘어난다.
소용돌이의 방향은 수평선, 수직선이 아닌 45도 사선을 기준으로 바뀐다.

따라서 이를 직관적으로 나타낼 수 있는 변수들을 도입해보자.

원점으로부터의 거리 layer := max(abs(y), abs(x))
파란 직선 $y=x$ 를 기준으로 하는 좌표 u := -y+x
빨간 직선 $y=-x$ 를 기준으로 하는 좌표 v := -y-x
(u, v의 방향은 소용돌이의 방향을 따라 정했다.)

이때, 층의 내벽의 길이를 side := 2*layer - 1라 하고,
u, v의 부호에 따라 8개의 구획으로 나누면 그 층에서 전진한 횟수 walk를 side, u, v의 값으로 나타낼 수 있다. 코드를 참고하자.

3. '예쁘게' 출력

소용돌이를 예쁘게 구하기 위해서는 출력할 범위의 소용돌이 값을 먼저 구한 뒤, 그 중 -부호를 포함해 가장 긴 문자열의 길이를 기준으로 패딩(padding)을 해야 한다.

출력할 데이터의 크기는 많아도 50 $\times$ 50 = 2500개이기 때문에 중복 계산해도 상관 없지만, 기왕이면 메모이제이션을 써보자.

코드 (Python)

def f(y, x):
    layer = max(abs(y), abs(x))
    if layer == 0:
        return 1
    
    side = 2*layer-1
    
    v, u = -y+x, -y-x
    walk = 0
    if v>0 and u<0:
        walk = v
    elif v>0 and u==0:
        walk = side + 1
    elif v>0 and u>0:
        walk = side + 1 + u
    elif v==0 and u>0:
        walk = 2*side + 2
    elif v<0 and u>0:
        walk = 2*side + 2 - v
    elif v<0 and u==0:
        walk = 3*side + 3
    elif v<0 and u<0:
        walk = 3*side + 3 - u
    else:   # v==0 and u<0
        walk = 4*side + 4

    return side*side + walk


r1, c1, r2, c2 = map(int, input().split())
A=dict()
for i, y in enumerate(range(r1, r2+1)):
    for j, x in enumerate(range(c1, c2+1)):
        A[(i, j)] = f(y, x)

maxlen = max({len(str(v)) for v in A.values()})
for i, _ in enumerate(range(r1, r2+1)):
    for j, x in enumerate(range(c1, c2+1)):
        v = A[(i, j)]
        vlen = len(str(v))
        print(' '*(maxlen-vlen)+str(v), end='')
        if x < c2:print(' ',end='')
    print()