SWEA 1954번: 달팽이 숫자 (D2) - Python 풀이

문제 설명

SW Expert Academy

달팽이는 1부터 N*N까지의 숫자가 시계방향으로 이루어져 있다.

다음과 같이 정수 N을 입력 받아 N크기의 달팽이를 출력하시오.

[예제]

N이 3일 경우,

N이 4일 경우,

[제약사항]

달팽이의 크기 N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10)

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스에는 N이 주어진다.

[출력]

각 줄은 '#t'로 시작하고, 다음 줄부터 빈칸을 사이에 두고 달팽이 숫자를 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

입력

2
3
4

출력

#1
1 2 3
8 9 4
7 6 5
#2
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

풀이 과정

아무래도 이 문제는 과소평가 당했습니다. D2라니요 ㅋㅋ

SWEA 사이트는 좋은 게 문제마다 댓글을 달 수가 있어서 사람들 반응을 볼 수 있는데 저처럼 생각하시는 분들이 꽤 있어 다행입니다.

일단 규칙 자체는 쉽게 찾을 수 있습니다. arr[0][0]에서 1로 시작해서, 열 1칸씩 증가 & 값 1씩 증가해서 채우다가 벽을 만나면(= N*N 범위를 벗어나면) 방향을 아래로 틉니다.

아래로 이동하면서 또 1씩 증가시키다가 벽을 만나면 왼쪽으로 방향을 틀고, 또 벽을 만나면 오른쪽으로 방향을 틉니다. 즉 방향은 오른쪽 → 아래쪽 → 왼쪽 → 위쪽 순으로 반복됩니다.

값이 N*N이 나오면 칸을 다 채웠으니 종료합니다.

“방향대로 1칸씩 이동, 값 1씩 증가, 범위 벗어나면 방향 전환” 이라는 구조가 반복되니 재귀로 풀고, 방향 전환을 구현하기 위해 dx, dy를 사용합니다.

정답 코드

T = int(input())
     
for test_case in range(1, T + 1):
    N = int(input())
    # 값을 채워야 할 2차원 배열, 0으로 초기화 해서 생성
    arr = [[0] * N for _ in range(N)]
    # 오른쪽, 아래쪽, 왼쪽, 위쪽 순으로 dx, dy 구성
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    # 재귀 함수
    def recursive_snail(x, y, d, num):
        # row = x, col = y 위치에 num 값으로 채웁니다
        arr[x][y] = num
        # 방향에 맞게 1칸 이동
        nx = x + dx[d]
        ny = y + dy[d]
         
        # N * N 값까지 채우면
        if num == N * N:
            # 프로그램 종료
            return
        # 0 <= nx < N, 0 <= ny < N 이 범위를 벗어났거나,
        # 범위 안이지만 arr[nx][ny] 값이 이미 채워진 상태라면
        if nx < 0 or nx >= N or ny < 0 or ny >= N or arr[nx][ny] != 0:
            # 방향을 전환합니다
            # 4개의 방향 안에서만 움직여야 하기 때문에 4로 나눈 나머지를 사용
            d = (d + 1) % 4
            # d 제외 지금 값 그대로 재귀 호출
            recursive_snail(x, y, d, num)
        # 범위 안이고, arr[nx][ny] 값이 아직 0이라면
        else:
            # nx, ny, num + 1 값으로 재귀 호출
            recursive_snail(nx, ny, d, num + 1)
         
    # (0, 0)에서 dx[0], dy[0], num = 1로 재귀 시작
    recursive_snail(0, 0, 0, 1)
    print("#%d" %test_case)
    for a in arr:
        # 언패킹 연산자 *로 1차원 배열 a의 요소를 하나씩 풀어서 출력
        print(*a)

이번에도 주석으로 열심히 설명했습니다.

recursive_snail의 2번째 if문에서 arr[nx][ny]가 0이 아닌지를 왜 확인해야 하냐면, 방향 전환을 해야 하는 케이스가 1. N * N 범위를 벗어날 때 2. 이미 채워진 값을 만났을 때로 2가지가 있기 때문입니다.

예를 들어 N = 3일 때, 3 찍고 아래로 방향 전환, 5 찍고 왼쪽으로 전환, 7 찍고 위쪽으로 전환합니다. 이때는 모두 1번의 케이스였습니다. 그 후 8 찍고 오른쪽으로 전환을 해야 하는데, 이때는 nx, ny가 N * N의 범위를 벗어난 게 아닙니다. 계속 위로 갈까 하다가 이미 채워진 ‘1’을 만난 거죠. 이는 2번 arr[nx][ny]가 0이 아닌 경우에 해당하고 이때에도 방향을 전환해 주어야 합니다.

이상입니다.