[Algorithm] 달팽이 배열(나선형 배열)

❗달팽이 배열

나선형으로 배열을 채우는 패턴으로 배열을 돌면서 값을 순서대로 채우는 배열을 말한다. 일반적으론 왼쪽 상단에서 시작해서 안쪽으로 채우는 경우가 많고, 변형으로 중앙에서 시작해서 바깥쪽으로 나가는 방식도 있다

 

 

❗좌측 상단에서 시작

n, m = map(int, input().split(" "))

graph = [[0 for _ in range(m)] for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
d = 0

x = 0
y = 0

graph[x][y] = 1
visited[x][y] = 1

for i in range(2, n * m+1):

    nx = x + dx[d]
    ny = y + dy[d]

    if not (0 <= nx and nx < n and 0 <= ny and ny < m and not visited[nx][ny]):
        d = (d + 1) % 4
        nx = x + dx[d]
        ny = y + dy[d]

    x = nx
    y = ny

    graph[x][y] = i
    visited[x][y] = 1

for row in graph:
    print(*row)

 

1. 시작점은 0, 0으로 d도 0으로 설정
2. graph와 visited에 시작점 설정
3. 채워넣을 값(i)을 for문 실행
4. nx와 ny가 범위 안에 없거나 방문한 경우에 방향을 수정하고 nx, ny를 다시 설정
5. x와 y를 nx와 ny로 업데이트
6. graph와 visited에 x와 y위치 값 업데이트

 

 

 

❗중앙에서 시작

n = int(input())

graph = [[0 for _ in range(n)] for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]

x = n // 2
y = n // 2

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
d = 0
dist = 1

graph[x][y] = 1
num = 2


while num <= n*n:
    # 같은 거리 2번
    for _ in range(2):
        for _ in range(dist):
            nx = x + dx[d]
            ny = y + dy[d]

            if  0<= nx and nx < n and 0<= ny and ny < n and not visited[nx][ny]:
                x = nx
                y = ny
                graph[x][y] = num
                num += 1
                visited[x][y] = 1
        d = (d+1)%4
    dist += 1


for row in graph:
    print(*row)

 

1. 시작점은 범위 크기 // 2, d(방향)은 0, dist(거리)는 1로 설정
2. num은 2부터 시작하며 n*n까지만 실행할 수 있게 하기
3. 같은 크기의 거리를 2번씩 실행
4. 그 안에서 dist만큼 값을 채워나가는 방식
5. nx, ny를 설정하고 범위 내에 있으며 방문하지 않은 경우만 x, y로 업데이트하고 graph의 값을 num으로 채움
6. 다음 순서를 위해 num+1
7. 거리만큼 실행 후엔 방향 변경
8. 2번 같은 방향으로 실행하면 dist+1