n*n 2차원 배열 달팽이 알고리즘 - 파이썬

n이 홀수인 경우 그리고 n*n인 2차원 배열인 경우에만 사용할 수 있는 코드 일듯하다.

달팽이가 벽에 부딪히거나 방향을 바꿔야 하는 경우 바뀔 방향은 고정적이라는 특성을 활용했다.

 

import copy

n = int(input())

arr = [[0 for _ in range(n)] for _ in range(n)]
dx = [0,-1,1,0,0]
dy = [0,0,0,-1,1]

check_arr = copy.deepcopy(arr)
check_arr[0][0] = 1
move_path_back=[[0,0,2]]
move_path_start=[[n//2,n//2,1]]

while True:
    before = move_path_back[-1]
    way = before[2]
    curr = [before[0]+dx[way], before[1]+dy[way],way]
    if curr[0] == n//2 and curr[1] == n//2:
        break
    if curr[0] < 0 or curr[0] >= n or curr[1] < 0 or curr[1] >= n or check_arr[curr[0]][curr[1]] == 1: #before의 방향을 수정해줘야함
        if way == 1: #to left 3
            move_path_back[-1][2] = 3
        if way == 2: #to right 4
            move_path_back[-1][2] = 4
        if way == 3: #to under 2
            move_path_back[-1][2] = 2
        if way == 4: # to up 1
            move_path_back[-1][2] = 1
        continue
    else:
        move_path_back.append(curr)
        check_arr[curr[0]][curr[1]] = 1

for i in range(len(move_path_back)-1,0,-1):
    curr = move_path_back[i].copy()
    next = move_path_back[i-1]
    if curr[0] > next[0]:
        curr[2] = 1
    if curr[0] < next[0]:
        curr[2] = 2
    if curr[1] > next[1]:
        curr[2] = 3
    if curr[1] < next[1]:
        curr[2] = 4
    move_path_start.append(curr)
move_path_start += move_path_back

for path in move_path_start:
    if path[2] == 1:
        arr[path[0]][path[1]] = '상'
    if path[2] == 2:
        arr[path[0]][path[1]] = '하'
    if path[2] == 3:
        arr[path[0]][path[1]] = '좌'
    if path[2] == 4:
        arr[path[0]][path[1]] = '우'
    for a in arr:
        print(a)
    print("==========================")
    print()

시작

다시 돌아오기

위와 같이 정 중앙에서 시작해 [0,0]에 도달하면 다시 돌아오는 과정을 거치는 코드다. 시작이 정중앙이다 보니 중앙에서부터 길을 구하려고 하니 생각할 부분이 너무 많았다.

 

그래서 그냥 돌아오는 길부터 먼저 구하고 그 길을 이용해서 시작하는 길을 구했다.