[알고리듬] #84 회돌이

[key word] 스파이럴, spiral

파이썬 실습창을 열 수 있습니다.실습창 열기

 

회돌이

회돌이(spiral)는 숫자 등을 소용돌이처럼 기억시키는 것입니다.

 

방향검사를 사용하면 간단하게 코딩할 수 있습니다.

∙list를 다음과 같이 준비합니다.

-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	0	0	0	0	0	0	0	0	-1
-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

 

• 실제 사용은 0이 기록된 곳입니다.
• 둘러싸고 있는 -1은 보초(sentinel)입니다.
  보초를 사용하면 편리한 경우가 많습니다.
  전체에 -1을 기억시키고, 사용할 곳은 0으로 바꾸었습니다.
• 진행 방법
  진행 방향에 숫자가 있으면 방향 전환하고, 없으면 현재 방향으로 진행합니다.
  (dir+1)%4는 0,1,2,3을 반복시켜서 방향을 전환합니다.

코딩하기

#---------------------------------------------------------------준비
di=(0,1,0,-1)                           #행 방향 체크 데이터
dj=(1,0,-1,0)                           #열 방향 체크 데이터
row,col=6,10                            #행, 열의 크기 
a=[[-1]*(col+2) for i in range(row+2)] 
for i in range(1,row+1):
    for j in range(1,col+1):
        a[i][j]=0
#----------------------------------------------------------------처리
i,j,dir=1,1,0                           #처음 기억시킬 곳과 방향
for k in range(1,row*col+1):            #기억시킬 값
    a[i][j]=k                           #값의 기억
    fi=i+di[dir]                        #진행을 확인할 행
    fj=j+dj[dir]                        #진행을 확인할 열
    if a[fi][fj]!=0: dir=(dir+1)%4      #방향바꿈
    i+=di[dir]                          #행의 진행
    j+=dj[dir]                          #열의 진행
#-----------------------------------------------------------------출력  
for i in range(1,row+1):
    for j in range(1,col+1):
        print(f'{a[i][j]:4}',end='')
    print()

 

역순 기억

역순으로 기억 시키려면 12번 줄을     a[i][j]=row*col+1-k  로 바꾸면 됩니다.

 

수고하셨습니다.

안녕!