[백준] 1913번 달팽이 파이썬 정답 코드

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

1913번: 달팽이

---

1. 접근 방식

• 빈 표에서 바깥쪽부터 숫자를 채워나가자.

목표는 위 그림의 왼쪽 초기 표 상태에서 오른쪽 표 상태로 만드는 것이다. 이를 위해서 왼쪽, 아래쪽, 오른쪽, 위쪽으로 4번에 나눠 값을 채워 넣는다.

처음에는 (0, 0)에 n² = 25를 넣는 것으로, 왼쪽부터 값을 채워 넣는다. 이때 열 j는 0으로 고정되어 있고, 행 i만 0에서 (n - 1) = 4까지 증가한다.

아래쪽은 행 i가 4로 고정되어 있고, 열 j는 1부터 4까지 순회한다. j가 0이 아니라 1부터 시작하는 이유는 이미 (4, 0)에 21이라는 값이 들어왔기 때문이다.

오른쪽은 열 j는 4로 고정, 행 i는 3부터 0까지 순회하면서 값을 채운다.

위쪽은 행 i는 0으로 고정, 열 j는 3부터 1까지 순회한다. 0을 확인하지 않는 이유는 이미 (0, 0)에 25 값이 들어 있기 때문이다.

 

• 위 코드를 재귀 함수로 만들자.

한 번 함수가 실행될 때마다 표의 테투리 한 줄이 완성된다. 따라서 재귀 함수를 사용하면 종료 조건에 도달할 때까지 표를 완성하게 된다.

재귀 함수의 종료 조건은 현재 i와 j가 n // 2와 동일할 때이다. 왜냐하면 1은 무조건 표의 중앙에 위치하기 때문이다.

 

 

2. 정답 코드

def make_table(i, j, length, count):
    if i == n//2 and j == n//2:
        array[i][j] = count
        return

    row, col = i, j
    
    # 왼쪽
    while i < length:
        array[i][j] = count
        i += 1
        count -= 1
    i -= 1
    j += 1
    
    # 아래쪽
    while j < length:
        array[i][j] = count
        j += 1
        count -= 1
    i -= 1
    j -= 1
    
    # 오른쪽
    while i > row - 1:
        array[i][j] = count
        i -= 1
        count -= 1
    i += 1
    j -= 1
    
    # 위쪽
    while j > col:
        array[i][j] = count
        j -= 1
        count -= 1

    make_table(row + 1, col + 1, length - 1, count)

def print_result():
    for i, arr in enumerate(array):
        if k in arr:
            position = (i + 1, arr.index(k) + 1)
        print(' '.join(list(map(str, arr))))
    print(position[0], position[1])

# main
n = int(input())
k = int(input())

array = [[0] * n for _ in range(n)]
make_table(0, 0, n, n**2)

print_result()

5월 초반에 포기했던 문제인데, 이번에 성공했다. 성장한 듯하여 몹시 뿌듯하다.

또한 위 코드의 실행 속도가 빠른 편이다. 백준 채점 결과를 보면 파이썬은 대개 800ms 이상이다.