[Algorithm] 이차원 배열 나선 순회

개요

최근 이차원 배열을 나선 순환하는 알고리즘 문제를 풀었다. 방법은 알았는데, 그걸 실제로 구현하는 것에서 약간 어려움이 있었어서 적절한 구현 방법을 정리해두려고 한다.

 

이 글에서 구현하고자 하는 것은 n 행, m 열로 이루어진 이차원 배열을 나선 순회하는 코드이다. 출발 시 이동 방향은 오른쪽이다.

 

 

 

방법

아이디어는 다음과 같다.

• 각 방향 별 끝 갑을 초기화한다.
• 끝에 다다랐을 때 끝 값을 갱신한다.

구현해 보자.

 

1. 배열 및 끝 값 초기화

# n행 m열 배열 초기화
spiral_list = [[0 for _ in range(m)] for _ in range(n)]

# 방향 별 끝 값
lp_left_side = 0
lp_right_side = m - 1
lp_up_side = 1  # i == 0 부터 순회 하므로 up의 초기 값은 1이 된다.
lp_down_side = n - 1

(0, 0)부터 출발하므로, 위로 이동하는 순간의 끝 값은 1이 되어야 한다. 즉, 위로 이동할 때 1행까지만 이동이 가능하다.

 

2. 이동 정보 초기화

# 0: right, 1: down, 2: left, 3: up
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
idx_direction = 0   # initialize to right

directions에는 이동하는 정도를 초기화한다. 순서대로 우하좌상 순서이며, idx_direction은 directions에서 현재 이동 방향을 지정하기 위한 값이다.

 

3. 현재 값 초기화

이동 순서 및 현재 위치를 초기화한다.

count = 1
i, j = 0, 0

 

3. 배열 순회

# 필요 이동 횟수 만큼 반복
while count <= n * m:
    # 이동
    spiral_list[i][j] = count
    # 다음 이동 순서 갱신
    count += 1
    
    # 진행방향의 끝에 도달하면 방향 전환
    if idx_direction == 0 and j == lp_right_side:
        idx_direction = (idx_direction + 1) % 4
        # 끝 값 갱신
        lp_right_side -= 1
    elif idx_direction == 1 and i == lp_down_side:
        idx_direction = (idx_direction + 1) % 4
        lp_down_side -= 1
    elif idx_direction == 2 and j == lp_left_side:
        idx_direction = (idx_direction + 1) % 4
        lp_left_side += 1
    elif idx_direction == 3 and i == lp_up_side:
        idx_direction = (idx_direction + 1) % 4
        lp_up_side += 1
    
    # 다음 방문 위치 설정
    i += directions[idx_direction][0]
    j += directions[idx_direction][1]

실행 준 배열은 아래와 같은 순서로 채워지게 된다.

 

 

실행 결과

최종적으로 나선 순회 결과는 다음과 같다. 

달팽이처럼 빙글빙글 잘 초기화된 모습을 확인할 수 있다.

 

 

문단 마지막 사용

* 정수를 나선형으로 배치하기