1913 달팽이 백준 (구현문제)
문제
홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.
| 9 | 2 | 3 |
| 8 | 1 | 4 |
| 7 | 6 | 5 |
| 25 | 10 | 11 | 12 | 13 |
| 24 | 9 | 2 | 3 | 14 |
| 23 | 8 | 1 | 4 | 15 |
| 22 | 7 | 6 | 5 | 16 |
| 21 | 20 | 19 | 18 | 17 |
N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.
입력
첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.
출력
N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.
정말 비효율적으로 어거지로 풀었다. ㅠㅠ
처음에 한 설계로는
처음 위치는 N//2,N//2로 고정되어있고, 방향 이동순서는 북 동 남 서 순서였다.
입력:
1.홀수인 자연수 N
2.N^2이하 자연수
출력:
1.표
2.자연수 좌표
N=1000정도 이고 2초제한이니 N^3미만 알고리즘을 써야겠다고 생각했다.
기본적으로 막힐때까지 범위로 북동남서를 돌면 될 줄 알았다.
부족했던것:
우선 설계나 구현 아이디어가 좀 많이 부족했다.
막힐때까지의 범위가 아니라 또아리틀듯이 이동하려면 숫자가 9,25일때 범위가 1에서 1개씩 증가했다.
잘 안됐던 문법으로는 join이 있다.
' '.join(map(str, array[i])) 를 쓰면 숫자 리스트의 배열들이
숫자만 공백으로 나눠져 출력된다.
그리고 생각보다 필요한 변수랑 아이디어도 많았다.
내가 추가한 알고리즘 생각은 홀수의 제곱수가 나올때마다 이동범위를 변경해주는 것이다.
숫자가 9가 되기 전까지는 달팽이의 이동경로는 시작 좌표의 x,y에서 차이가 1이상 나지 않는다.
이점을 이용해서 9,25,49 ''' 이런식으로 숫자가 나올때 차이가 날 수 있는 범위를 증가시켜줬다.
다만 더 생각해야 될 부분은 이동예상 다음 좌표가 0을 넘어가면 -1이 되는데 이러면 절대값을 활용해도
범위를 구하기가 어렵다. 그래서 이런 경우만 아예 다음 예상 좌표 모두 >=0인 조건을 추가해서
다음 예상좌표의 x,y값과 시작좌표의x,y값의 각각 거리차이를 정확하게 구하려고 했다.
더 나은 풀이를 참고해야겠다.
풀이
import math
#입력
n=int(input())
#n2이하 자연수
num=int(input())
numx=0
numy=0
#가변하는 범위 변수
level=1
array=[[0]*n for _ in range(n)]
#이동을 위한 배열
#현재 이동방향도
dx=[-1,0,1,0]
dy=[0,1,0,-1]
now=0
#시작 좌표
startx=n//2
starty=n//2
#현재 좌표
nx=ny=n//2
array[nx][ny]=1
#이동해야될 다음좌표 함수
#제곱수
squareNum=3
def move(x,y,n):
#현재 방향을 기준으로 1. 밖으로 벗어나면 방향 변경해서 반영 2.안나가면 계속
global now,nx,ny,dx,dy
# print("1.xy"+str(x)+str(y))
kx = x + dx[now]
ky = y + dy[now]
# print("2.kxky="+str(kx)+str(ky))
if kx>=0 and ky>=0 and (0<= abs( abs (kx) - startx )<=level) and (0<=abs( abs(ky) - starty) <=level):
nx=kx
ny=ky
return [kx,ky]
else:
if now!=3:
now+=1
else:
now=0
nx = x + dx[now]
ny = y + dy[now]
return [nx,ny]
for i in range(2,n*n+1):
#다음 인덱스 구하기
arr=move(nx,ny,n)
#print("3.arr"+str(arr[0])+str(arr[1]))
array[nx][ny]=i
#print("4.i="+str(i))
if int(math.sqrt(i) )==squareNum:
level+=1
squareNum+=2
# print("level변경 "+str(level))
if num==1:
numx=(n-1)//2
numy=(n-1)//2
elif num==i:
numx=nx
numy=ny
for i in range(n):
print(' '.join(map(str,array[i]) ) )
print(numx+1,numy+1,sep=" ")