[백준 1913번] 달팽이 - 파이썬

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

💡문제 분석 요약

구현 문제이다. 달팽이가 배열의 가운데서 시작해, 시계방향으로 숫자를 1씩 키우며 움직인다. 최종적으로 완성된 배열과 같이 입력받은 숫자의 좌표를 출력하라.

 

💡알고리즘 설계

1. 달팽이가 지나갈 배열을 0으로 초기화한다.

2. 달팽이가 (0,0) 위치에서 N*N을 저장하며 시작한다.

3. 숫자를 하나씩 줄이며, 다음 위치가 배열의 안이며, 다음 위치의 배열에 0이 저장되어 있다면 그 위치로 이동하여 줄어든 숫자를 저장한다.

4. 다음 위치가 배열 밖이거나 이미 다른 숫자로 채워져 있다면 방향을 바꾸고, 다시 이동한다. 방향은 시계 반대 방향으로 변경한다. 

 

💡코드

import sys
input = sys.stdin.readline

N = int(input())
pos = int(input())

arr=[[0 for i in range(N)] for j in range(N)]
col, row, pos_x, pox_y, dir = 0, 0, 0, 0, 0
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]

for i in range(N*N, 0, -1):
    arr[row][col]=i
    if i==pos:
        pos_x=col+1
        pos_y=row+1
    if N>row+dy[dir]>=0 and N>col+dx[dir]>=0 and arr[row+dy[dir]][col+dx[dir]]==0:
        col+=dx[dir]
        row+=dy[dir]
    else:
        dir+=1
        if dir==4:
            dir=0
        col+=dx[dir]
        row+=dy[dir]
    
for i in arr:
    for j in i:
        print(j, end=' ')
    print('')
print(pos_y, pos_x)

💡시간복잡도

for문을 이용하므로 O(N)이다. 그러나 for문 안에 조건문이 많아 시간이 오래 걸린다.

 

💡 느낀점 or 기억할 정보

시간이 엄청 오래 걸렸는데 더 빨리 구현할 수 있는 방법이 없을지 궁금하다.