[BOJ 1913] 달팽이

문제 출처 : https://www.acmicpc.net/problem/1913

풀이

홀수인 N 이 주어지므로, 시작점인 1의 위치는 항상 ($N \over 2$, $N \over 2$) 이다. (0-indexed 배열의 경우) 그 후 위로 한 칸 이동한 다음 시계방향으로 돌면서 다음 숫자가 채워진다. (2, 3, …, $N^2$) 문제의 조건에서 $N \leq 999$ 이므로, $1000 \times 1000$ 배열을 전역으로 선언하여 쉽게 구현 가능하다.

또는 (0,0) 의 위치에서 항상 N^2 으로 시작하는 것에서 착안할 수 있다.

코드

if __name__ == "__main__":
    N = int(input())
    M = int(input())

    a = [[0]*N for _ in range(N)]

    dy = [1,0,-1,0]
    dx = [0,1,0,-1]
    s = N*N
    y = -1
    x = 0
    dir = 0
    ty = 0
    tx = 0
    while s > 0:
      ny = y + dy[dir]
      nx = x + dx[dir]
      if (ny<0 or ny>=N or nx<0 or nx>=N) or a[ny][nx]!=0:
        dir = (dir + 1) % 4
        continue
      y = ny
      x = nx
      a[ny][nx] = s
      if s == M:
        ty = y
        tx = x
      s -= 1

    for i in range(N):
      for j in range(N):
        print(str(a[i][j]), end=" ")
      print("")
    print(str(ty+1) + " " + str(tx+1))

개선할 점

다시 python 으로 PS 연습부터 해보자