[백준 1022번 - 소용돌이 예쁘게 출력하기] - Python

문제 설명

문제 난이도 : Gold  IV 

자세한 문제 설명 : 더보기 클릭!

문제 :

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

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 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가 주어진다.

출력 : 

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

My Code

r1,c1,r2,c2 = map(int,input().split())
length = max(abs(r1),abs(r2),abs(c1),abs(c2))
length = length*2 +1 # 모눈종이 행과 열의 길이

# arr에 필요한 부분만 구하기
arr = [[0 for _ in range(c2-c1+1)] for _ in range(r2 - r1 + 1)]

x,y = length//2,length//2 # 시작 지점

arr_n = 1 # 소용돌이 순서 값 (배열에 저장되는 값)

increment = 1 # 증가횟수
flag = True # 두번 진행할때마다 증가횟수 1증가 체크

dx = [0,-1,0,1]
dy = [1,0,-1,0]
rotate = 0 # 회전 방향

# arr의 인덱스 번호로 변경
r1 += length//2
r2 += length//2
c1 += length//2
c2 += length//2

while(arr_n < length*length):
    if((rotate==0 and r1<=x<=r2 and (y<=c2 or c1<=y+dy[rotate]*(increment-1))) or
      (rotate==1 and c1<=y<=c2 and (x>=r1 or r2>=x+dx[rotate]*(increment-1))) or
      (rotate==2 and r1<=x<=r2 and (y>=c1 or c2>=y+dy[rotate]*(increment-1))) or
      (rotate==3 and c1<=y<=c2 and (x<=r2 or r1<=x+dx[rotate]*(increment-1)))):
        
        for i in range(increment):
            if(r1<=x<=r2 and c1<=y<=c2):
                arr[x-r1][y-c1] = arr_n
            x = x+dx[rotate]
            y = y+dy[rotate]
            arr_n += 1
    else:
        x = x+dx[rotate]*increment
        y = y+dy[rotate]*increment
        arr_n += increment
                
    #회전
    rotate = (rotate+1)%4

    if(flag == True):
        flag = False
    else:
        increment += 1
        flag = True
    
if(r1==r2==c1==c2==0):
    print(1)
    
else:
    digit = 0 #자리수
    maxValue = max(max(arr)) # arr 전체에서 가장 큰 값
    
    while(maxValue>0): #자리수 구하기
        digit += 1
        maxValue = maxValue // 10
    
    for i in range(r2 - r1 + 1):
        for j in range(c2-c1+1):
            if(j == c2-c1):
                print(f'%{digit}d'%arr[i][j],end="")
            else:
                print(f'%{digit}d'%arr[i][j],end=" ")
        print()

 

arr은 모눈종이에서 필요한 부분을 저장하는 배열로 최소 크기를 구하도록 구현하였다.

 

arr_n은 소용돌이의 순서로 1부터 차례대로 배열에 저장된다.

예시 사진

예시 사진을 살펴보면 1부터 2까지 1칸, 2부터 3까지 1칸, 3부터 5까지 2칸, 5부터 7까지 2칸, 7부터 10까지 3칸....

1칸,1칸, 2칸,2칸, 3칸,3칸, 4칸...순서로 움직이고 회전하는것을 알 수 있다.

increment는 여기서 움직이는 칸수를 의미하며,

flag는 2번씩 반복한 뒤 움직이는 칸수(increment)가 1 증가하기 때문에 2번 반복했는지 check하는 역할이다.

 

while문은 배열의 크기만큼 반복하며

if문에서는 현재 위치부터 회전하기 전까지의 위치 사이에 출력 할 위치의 소용돌이가 존재하는지 체크한다.

존재하는 경우 한칸씩 움직이며 사용자가 출력 할 위치의 소용돌이의 경우 배열에 저장한다.

존재하지 않는 경우 다음 회전까지 한번에 이동한다.

 

문제가 복잡해 설명이 쉽지 않다... 죄송합니다...

궁금한 점 댓글 달아주시면 추가로 설명해드릴게요!!

Answer

# 입력
-1 -2 -1 1
# 출력
18  5  4  3

# 입력
-3 -3 2 0
# 출력
37 36 35 34
38 17 16 15
39 18  5  4
40 19  6  1
41 20  7  8
42 21 22 23

TIL

• 자연수 글자 수 구하기

digit = 0
num = 100
while(num>0):
	digit += 1
    num = num // 10
    
print(num)

num = 100
print(len(str(num)))

한 자리수씩 체크하는 것 보다는 string으로 바꾼 뒤 len()을 활용해 크기를 구하는 것이 파이썬다운 코드이다.

 

• 모눈종이에 1부터 돌아가며 하나씩 출력하는 경우 시간 초과가 발생해 필요한 부분만 배열에 저장해야돼 난이도가 높았다...
• 바보같이 r1, c1, r2, c2 이 모두 0인 경우 1을 출력해야되는데 r1, c1, r2, c2이 모두 같은 경우까지 1을 출력해서 시간이 오래걸렸다. 반례 찾아주신 siyamaki 님 감사합니다.....ㅜ

다신 보지 말자~~

 

시도 결과

Short Coding

a,x,b,y=map(int,input().split())
U=[]

for i in range(a,b+1):
    u=[]
    U+=[u]
    
    for j in range(x,y+1):
        k=2*max(-i,i,-j,j)
        u+=[1+k*k+(-1)**(i<j)*(i+j+k)]
        
for z in U:
    print(*[f"%{len(str(max(U[0]+u)))}d"%i for i in z])

다른 사람의 코드로 복잡한 구현을 이렇게 짧게 구현할 수 있다는게 대단하다...

해당하는 위치의 숫자를 공식으로 직접 구현한 코드이다.

 

---

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

 

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