[백준] 1913. 구현_달팽이 - Python

문제

홀수인 자연수 N(3≤N≤999)이 주어지면, 다음과 같이 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이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

 

★ 시작하기 전에

DP (동적계획법)에 대한 학습 이후로 동적 계획법을 사용하면 어떨까라는 생각을 했다. 1단계를 통해 2단계를 만들고 2단계를 통해 3단계를 만드는 식으로 하면 되지 않을까?

첫 시도는 이러하였다... 하지만 시간 초과!!!

import sys

input = sys.stdin.readline

n = int(input())
check = int(input())

ind = (n-1)//2
dp = []
dp.append([[1]])
dp.append([[9, 2, 3], [8, 1, 4], [7, 6, 5]])

if ind <= 1:
    pass
else:
    for k in range(2, ind+1):
        before = dp[k-1]
        result = [[]] + before +[[]]
        for i in range(2*k+1):
            result[i] = [(2*k+1)**2 - i] + result[i]
        for j in range(2*k+1-1):
            result[0].append((2*k-1)**2 + (j+1))
        for m in range(1, 2*k +1):
            result[-1].append(result[-1][0]-m)
        for o in range(1, 2*k):
            result[o].append(result[0][-1]+ o)
        dp.append(result)
ans = dp[ind]
result = []
for a in range(n):
    for b in range(n):
        if ans[a][b] == check:
            result.append((a+1, b+1))

for step in ans:
    print(' '.join((str(step)[1:-1].split(', '))))
print(result[0][0], result[0][1])

● 이렇게 풀면 안되겟구나 생각하며 4방향으로 공통된 작업을 하기 때문에 4방향을 한세트로 밖에서 안으로 같은 작업을 하게 하면 되지 않을까 라는 생각을 했다. 그러나 구현.... 하기가 쉽지 않았다.

생각은 했다.. 근데 만들어지지 않았다. 결국 내 생각을 구현해낸 코드를 익히고 또 외워버렸다.

import sys

input = sys.stdin.readline
n = int(input())
m = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]

dr = [0, 1, 0, -1] # 오른쪽, 아래쪽, 왼쪽, 위쪽 순서
dc = [1, 0, -1, 0]

r = n//2  # 시작 row
c = n//2  # 시작 column
num = 1  # 해당 위치에 들어갈 숫자 1씩 증가 예정
len = 0  # 특정 방향으로 이동할 길이 얼마나 더할 것인가. for 문으로 동일 작업 수행 가능.

board[r][c] = num

while True:
    for i in range(4):
        for _ in range(len):  # 특정 방향으로 한칸씩 이동하며 숫자 입력
            r+=dr[i]
            c+=dc[i]
            num+=1
            board[r][c]=num
            if num==m:  # 찾을 번호의 인덱스 저장
                ans = [r+1, c+1]

    if r==c==0:
        break
    r -= 1
    c -= 1
    len += 2

for i in range(n):
    print(*board[i])
print(*ans)

어떻게 달팽이 순회를 할지, 정말 궁금했는데 확실한 풀이 같다. 얼마나 해야 이런 구현을 해낼 수 있을까. 다음번 이런 경우는 구현할 수 있을 것이다. 믿는다!!!