[BOJ-1022] 소용돌이 예쁘게 출력하기

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

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

---

[풀이]

소용돌이의 위치에 따라서 왜 이 값이 나오는지 규칙성을 확인하면

풀 수 있다!

 

실제로 이 풀이는 내가 직접 생각해서 푼 풀이가 아니다.

블로그를 참고했다..ㅠ

블로그의 저자의 간결하고 명쾌한 코드.. 배워간다. ㅠㅠ

 

내가 시도한 코드와 다르게 (r1,c1), (r2,c2)의 위치를 변경하지 말고 그대로 둔다.

그리고 이 풀이는 점의 위치값에 따라 나오는 값을 도출했는데.

진짜 봐도봐도 명쾌하다. 

 

참고한 블로그와 내코드가 다른 부분은 자리수계산 getDigit()이다.

---

[성공코드 Python]

import sys
input=sys.stdin.readline

def getValue(r,c):
    n=max(abs(r), abs(c))
    last= 2*n+1
    last= last**2

    if r==n:#아래 변
        return last-(n-c)
    elif c==-n:#왼쪽 변
        return last-(2*n)-(n-r)
    elif r==-n:#윗 변
        return last-(4*n)-(n+c)
    else: #오른쪽 변
        return last-(6*n)-(n+r)

#자리수 계산
def getDigit(val):
    return len(str(val))

r1, c1, r2, c2=map(int, input().strip().split())

max_len=0
for y in range(r1, r2+1):
    for x in range(c1, c2+1):
        max_len=max( max_len, getDigit(getValue(y,x)) )

output=[]
for y in range(r1, r2+1):
    for x in range(c1, c2+1):
        output.append(f'{getValue(y,x): >{max_len}} ')
    output.append('\n')
        
#소용돌이 출력
sys.stdout.write(''.join(output))

 

[참고 블로그]

https://haedallog.tistory.com/135

[BOJ] 1022번 소용돌이 예쁘게 출력하기

 

---

[실패코드 python]

이유: 런타임 에러

import sys
input=sys.stdin.readline

def isAllVisited(visited):
    global ROW, COL
    for y in range(ROW):
        for x in range(COL):
            if not visited[y][x]:
                return False
    return True

def isRange(y,x):
    global ROW, COL
    if (y>=0 and y<ROW) and (x>=0 and x<COL):
        return True
    return False

r1, c1, r2, c2=map(int, input().strip().split())
ROW, COL=r2-r1+1, c2-c1+1

#소용돌이 입력

Round=1 ## 오른쪽/위/왼쪽 : 2*바퀴수-1  , 아래: 2*바퀴수-2
longest_num_len=0

cury, curx= ROW-1-r2, COL-1-c2 #소용돌이 시작위치
last_y, last_x = cury, curx #마지막 위치(배열에 입력한 마지막위치)

visited=[[False]*COL for _ in range(ROW)]
MAP=[ [0]*COL for _ in range(ROW)]

MAP[cury][curx]=1
visited[cury][curx]=True
now=2

while True:
    # visited가 모두 다 채워졌는가?
    if isAllVisited(visited):
        longest_num_len=len(str(MAP[last_y][last_x]))
        break

    #아래방향으로 이동
    for i in range(0,Round*2-2):
        cury=cury+1
        if isRange(cury, curx):
            MAP[cury][curx]=now
            visited[cury][curx]=True
            last_y, last_x= cury, curx
        now+=1
        
    #오른쪽으로 이동
    for i in range(0,Round*2-1):
        curx=curx+1
        if isRange(cury, curx):
            MAP[cury][curx]=now
            visited[cury][curx]=True
            last_y, last_x= cury, curx
        now+=1
               
    #위로 이동
    for i in range(0,Round*2-1):
        cury=cury-1
        if isRange(cury, curx):
            MAP[cury][curx]=now
            visited[cury][curx]=True
            last_y, last_x= cury, curx
        now+=1
        
    #왼쪽으로 이동
    for i in range(Round*2):
        curx=curx-1
        if isRange(cury, curx):
            MAP[cury][curx]=now
            visited[cury][curx]=True
            last_y, last_x= cury, curx
        now+=1

    #다음라운드로 왼쪽으로 이동
    Round+=1


#배열의 숫자의 길이에 따라서 다르게 나타내기
for y in range(ROW):
    for x in range(COL):
        now_len=len(str(MAP[y][x]))
        MAP[y][x]=' '*(longest_num_len - now_len)+str(MAP[y][x])

#소용돌이 출력
for y in range(ROW):
    print(' '.join(MAP[y]))

 

[나의 접근방법]

(1) 시작점 찾기 및 시작점 초기화

나는 (r1,c1)을 (0,0)으로 간주했다.

즉 r2-r1+1행 c2-c1+1열 2차원행렬로 나타냈다.

ROW=r2-r1+1

COL=c2-c1+1

 

그리고 소용돌이 시작위치인 (0,0)은 (ROW-1-r2, COL-1-c2)로 변경하여 나타냈다.

시작점의 위치를 방문하고, 값을 초기화했다.

그리고 now=2를 시작점으로 (2)단계를 실행했다.

 

(2) 모든배열이 다 채워질때까지(모든 배열원소가 다 방문될때까지) 계속 진행

일단은 나는 모든 배열원소가 방문될 때까지 확인하는 연산을 했다.

 

(2-1) ROW행 COL열 배열에 적합한 위치인지 확인 (isRange)

 

배열에 해당하는 위치 인지 확인(isRange) 한다.

isRange 결과와 상관없이 now값을 계속 카운트했다.

 

만일 isRange가 True일 경우에는

방문리스트(visited)를 True로 변경하고, 해당 위치에 값을 now값을 넣었다.

그리고 last_y, last_x 를 갱신했다.

last_y, last_x는 isRange()가 True일때 위치를 의미한다.

실제로는 MAP[last_y][last_x]에 해당하는 값의 길이를 구하기 위해서다.

즉, 배열에 저장된 값들의 길이중 가장 큰 값을 구하기 위해서다.

 

(2-2) 소용돌이 규칙

소용돌이에서 규칙이 보였다.

나는 바퀴수를 Round 로 표현했다.

 

첫번째 바퀴(Round=1)는

5 4 3

  1 2 이다.

 

즉, 아래방향: 0번 / 오른쪽, 위쪽방향: 1번  / 왼쪽: 2번 이동 했다.

 

 

2번째 바퀴(Round=2)는

17 16   15  14  13

      5    4    3  12

      6    1    2  11

      7    8    9  10 이다.

 

아래방향: 2번 / 오른쪽, 위쪽방향: 3번 / 왼쪽: 4번 이동했다.

 

여기서 규칙이 보였다.

아래방향: Round*2 -2 번

오른쪽, 위쪽방향: Round*2 -1 번

왼쪽방향: Round*2 번

 

(3) MAP에 입력된 값들중 가장 큰 값의 길이를 구한 뒤에 포맷팅 조정

모든 방문리스트가 방문될때까지 진행하며

모든 방문리스트 방물될때 마지막 last_y, last_x의 값이 가장 최댓값이며

길이가 가장 길다고 생각했다. 그길이를 나는 longest_num_len으로 했다.

 

그리고 이후 MAP의 모든 원소를 탐색하여

MAP[y][x] 길이를 구한다.

여기서 길이가 longest_num_len보다 작으면 차이만큼 왼쪽에 ' '을 넣었다.

---

[런타임에러 결과에 대한 나의 고찰]

r1, c1은 배열의 가장왼쪽의 위칸의 위치를 뜻하고

r2, c2는 배열의 가장오른쪽의 아래칸의 위치를 뜻한다.

 

여기서 고려해야할게

위치 (r1,c1), (r2,c2)가 (-5000, -5000), (5000, 5000)이라면?

위의 코드 방식으로 한다면 ROW=10000, COL=10000이 되는 셈이다.

그리고 행과 열의 범위는 0~9999

 

내가 생각한 에러는

(1) 이중 for문의 연산이 많다. 특히 이중 for문을 이용한 방문리스트 탐색

방문리스트의 모든원소가 True일 때를 찾는 과정에서

visited가 없을때까지 했는데 여기서 계속 잡아 먹은게 아닌가싶다.

(r1,c1), (r2,c2)가 (-5000, -5000), (5000, 5000)일때

MAP의 행열의 길이는 10000이므로 시간복잡도가 10000^2 번의 연산을 해야한다.

 

(2) 잘못된 출력형식

그리고 무엇보다도 흐트러진 소용돌이가 문제였다.

C,C++처럼 printf("%4d", MAP[y][x]); 이런 기능이 없다.

입력포맷을 맞추는 것에서 틀렸다.

width개수만큼의 글자길이로하고

message가 width값보다 작을때, message를 입력하고 남은 글자는 빈공간으로 한다.

화살표방향(<)은 빈칸을 채우는 방향이다.

mesage는 왼쪽부터 쭉 적혀있다.

 

 

python 입력 포맷 형식 맞추기 위한 참고자료이다.

https://stackoverflow.com/questions/5676646/how-can-i-fill-out-a-python-string-with-spaces

How can I fill out a Python string with spaces?

 

스스로는 어려울 거같아서 푼사람들의 블로그를 참고해야될 것 같다.

---