프로그래머스 삼각 달팽이

문제 풀이

1. 달팽이는 아래방향, 오른쪽 방향, 대각선(왼쪽 위) 방향 이 세가지를 번갈아 움직입니다.

  - 따라서 방향을 바꿀 때마다 check 변수에 1씩 더해주며, check mod 3이 방향이 됩니다.

2. 편의상 정사각형에서 움직인다고 생각하고 풀었습니다.

3. 아래로 움직일 때의 경우의 수를 생각해보면 다음과 같습니다.

  3-1) 끝까지 왔거나, 아래 방향의 칸이 0이 아닌 경우 : 방향을 오른쪽으로 바꾼 후, 오른쪽으로 한칸 움직인 후, 해당 칸을 현재 값으로 바꿔줍니다..

  3-2) 아래 방향의 칸의 값이 0인 경우 : 아래로 이동 후, 아래 칸의 값을 현재 값으로 바꿔줍니다.

4. 3의 과정을 오른쪽 방향, 대각선 방향에 대해서도 구현해 줍니다.

5. 밑변의 길이가 n일 때, 총 칸의 수 tot(n)은 다음의 재귀식으로 나타낼 수 있습니다.

  tot(n) = tot(n-1) + 1 , tot(1) = 1

  예를 들어, n=2일 때의 칸의 수는 tot(1) + 2 = 3이고, n=3일 때의 칸의 수는 tot(3) = tot(2) + 3 = 6입니다.

Python Code

def solution(n):
    direction = ['down','right','diagonal']
    check = 0
    answer = []
    square = [[0 for i in range(n)] for j in range(n)]
    i,j = 0,0
    square[j][i] = 1
    tot = sum(i for i in range(1,n+1))
    for s in range(2,tot+1):
        d = direction[check%3]
        if d == 'down':
            if j+1==n or square[j+1][i] != 0:
                check += 1
                square[j][i+1] = s
                i += 1
            else:
                square[j+1][i] = s
                j += 1
        elif d == 'right':
            if i+1 == n or square[j][i+1] != 0 :
                check += 1
                square[j-1][i-1] = s
                j-=1
                i-=1
            else :
                square[j][i+1] = s
                i += 1
        else :
            if square[j-1][i-1] != 0:
                check +=1
                square[j+1][i] = s
                j += 1
            else :
                square[j-1][i-1] = s
                j -= 1
                i -= 1
    for i,v in enumerate(square):
        answer += v[:i+1]
    return answer
 
 

Line 8 : 과정 5의 재귀식을 표현한 값입니다.

Line 37 : 사각형에서 필요한 부분만 잘라 answer에 붙여줍니다.

문제 링크

코딩테스트 연습 - 삼각 달팽이