[Python] 백준 - 1913 달팽이(기초 배열다루기)

  문제

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

 

🔹 문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

 

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

 

🔹 입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

🔹 출력

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

 

  풀이 방법

 

🔹 이차원 배열 구현

🔹 DFS 없이 가능하다

🔹 (0,0)에서 시작해 [하 → 우 → 상 → 좌] 방향으로 이동하며 배열을 채운다.

• 방향에 따라 순차적으로 진행하며, 벽에 부딪히면 방향을 바꾼다.
  (배열의 범위를 넘어서거나, 이미 해당 위치의 값이 채워진 경우 벽으로 간주.)
• 방향을 바꾸면, 다시 위치값을 지정한다.
• 방향 변경 시, 0 → 1 → 2 → 3 (하우상좌) 진행 후 다시 아래 방향(인덱스 0)으로 돌아가야하므로, 나머지를 활용
  (0,1,2,3), (4,5,6,7) → %4 → (0,1,2,3)
• 문제에서 정한 값(target)이 나오면 해당 위치 저장.

 

  구현 코드

import sys
n = int(sys.stdin.readline())
target = int(sys.stdin.readline())
arr = [[0] * n for _ in range(n)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
x,y = 0,0
cnt = n**2
d = 0
x_,y_ = 0,0

while cnt>0:
    arr[x][y] = cnt
    if cnt == target:
        x_,y_ = x+1,y+1
    cnt-=1
    nx = x+dx[d]
    ny = y+dy[d]
    if nx < 0 or nx >= n or ny <0 or ny >= n or arr[nx][ny]!=0:
        d = (d+1)%4
        nx = x+dx[d]
        ny = y+dy[d]
    x,y = nx,ny

for row in arr:
    print(*row)
print(x_, y_)

 

  실행 결과

 

  💡

🔹 시작점 위치(초기 x,y 선언)와 진행 방향(dx,dy), 배열에 넣는 값(cnt)을 변형하여 다양한 모양의 달팽이 배열을 만들 수 있다.