SWEA 1954. 달팽이 숫자 (Python, 구현, D2)

SWEA 1954. 달팽이 숫자 문제 바로가기

문제 접근

달팽이 숫자란 1씩 증가하는 수열을 달팽이 모양으로 출력하는 것을 말한다.
ex)
1 2 3
8 9 4
7 6 5

끝에 닿으면 방향이 일정하게 바뀌는 규칙이 존재하기 때문에 재귀함수로 풀어야겠다고 먼저 생각이 들었다.
파라미터로는 방향과, 숫자, 좌표를 전달해야 이를 구현할 수 있다.

문제 풀이

달팽이 숫자의 방향은 일정하게 우,하,좌,상 순서로 변경된다. 따라서 이를 dx,dy리스트에 넣어두고 방향 인덱스를 1씩 증가시키며 4로 나머지를 구해주면 일정한 순서로 방향을 변경시킬 수 있다.

따라서 일정한 방향으로 나아가다가, 2차원 배열의 끝을 만나거나 혹은 이미 숫자를 넣은 부분을 만나게 되면 방향을 오른쪽으로 변경하고 다시 진행하는 함수를 구현했다.

가장 중요한 종료조건은 이 달팽이 수열은 N*N의 2차원 배열을 모두 채우는 것이므로 현재 숫자가 N*N이 된다면 재귀함수를 종료하도록 설정했다.

    dx = [0,1,0,-1] # 우하좌상
    dy = [1,0,-1,0]
    def snail(x,y,d,num):
        pan[x][y] = num
        nx = x + dx[d]
        ny = y + dy[d]
        if num==N*N:
            return
        if nx < 0 or ny <0 or nx>=N or ny >= N or pan[nx][ny]!=0: # 끝에 도달하면 방향 전환
            d = (d+1)%4
            snail(x,y,d,num)
        else: 
            snail(nx,ny,d,num+1)

제출 코드

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    pan = [[0 for i in range(N)] for j in range(N)]
    dx = [0,1,0,-1] # 우하좌상
    dy = [1,0,-1,0]
    def snail(x,y,d,num):
        pan[x][y] = num
        nx = x + dx[d]
        ny = y + dy[d]
        if num==N*N:
            return
        if nx < 0 or ny <0 or nx>=N or ny >= N or pan[nx][ny]!=0: # 끝에 도달하면 방향 전환
            d = (d+1)%4
            snail(x,y,d,num)
        else: 
            snail(nx,ny,d,num+1)
            
    
    snail(0,0,0,1)
    print(f'#{test_case}')
    for i in range(N):
        for j in range(N):
            print(pan[i][j], end=" ")
        print()