[코테] 탐색구현 - 삼각 달팽이[프로그래머스]

문제:

출처: 프로그래머스 - 삼각 달팽이 : https://school.programmers.co.kr/learn/courses/30/lessons/68645#qna

풀이:

탐색의 순서를 구현할 수 있는지 묻는 문제다.
제일 위부터 아래까지 문제에서 제시하는 순서대로 수를 채웠을 경우에 다른 특정한 규칙이 보이지 않는다. 다시 말해서 문제에서 제시하는 순서대로 수를 채워넣을 수 있는 구현을 할 수 있는지 묻는 문제다.
문제에서의 그림과 같이 2차원 리스트를 생성하고, 제시하는 순서에 따라서 2차원 리스트에 수를 채워넣고, 채워진 2차원 리스트를 순서대로 반환하면 된다.

1. 수를 채워넣을 때에는 규칙성이 존재하는데 n = 4 라면 제일 먼저 아래로 4, 오른쪽으로 3, 왼쪽 대각선 위로 2, 그리고 다시 아래로 1의 순서를 가진다. 즉 방향이 전환될 때 주어진 n에서 부터 하나씩 순차적으로 -1씩 수가 줄어드는 것을 볼 수 있다.
2. 2중 반복문을 통해서 주어진 수부터 시작해서 반복문을 작성하면 되는데, 방향 전환을 몇 번 할 것인지 확인해야 한다. 방향은 총 3가지(아래, 오른쪽, 왼쪽 대각선 위)로 주어진 n에서 하나씩 차감될 때마다 순서대로 3가지의 방향이 사용이 되니 n = 4인 경우 방향의 변환도 4번을 할 수 있도록 한다.(4번째는 다시 아래로 향한다)
3. 시작점은 (0, 0)으로 시작하면 3번 진출만에 4까지 오고 5번째 진출도 아래로 향하게 되니 범위를 벗어나지 않도록 장치해 준다. 다른 방법으로는 처음은 무조건 아래로 시작하니 출발점을 (-1, 0)으로 삼아서 (0, 0)이 첫 번째 진출한 수가 되도록 설정해도 된다.

코드:

def solution(n):
    answer = []
    board = [[0] * i for i in range(1, n + 1)] # 문제에서 제시하는 크기 만큼의 2차원 리스트 생성
    step = [(1, 0), (0, 1), (-1, -1)] # 방향순서
    steps = step * ((n // 3) + 1) # 방향이 몇 번 바뀌는지 확인하여 길이를 늘려준다. 방향 순서는 바뀌지 않는다.
    board[0][0] = 1 # 출발점
    x, y = 0, 0 # 출발점 좌표
    k = 0 # 방향전환을 할 때 방향을 설정한다.
    
    for i in range(n, 0, -1): # 진출하는 횟수는 n에서 시작하여 하나씩 차감되어 진출하도록
        for j in range(i): # 같은 방향으로 진출하는 횟수는 i 
            nx = x + steps[k][0] # 도착지점의 좌표
            ny = y + steps[k][1]
            if 0 <= nx < n and 0 <= ny < n:
                board[nx][ny] = board[x][y] + 1
                x = nx # x, y를 다시 출발좌표로 만들기
                y = ny
        k += 1 # 한 번의 진출이 끝났으면 방향을 전환하기 위해 방향 순서를 1 올려준다.
        
    for i in board:
        answer.extend(i)
    return answer

같지만 다른 코드.
범위를 설정하지 않고 문제처럼 n부터 시작해서 방향이 바뀌도록

def solution(n):
    answer = []
    board = [[0] * i for i in range(1, n + 1)]
    step = [(1, 0), (0, 1), (-1, -1)]
    steps = step * ((n // 3) + 1)
    board[0][0] = 1
    x, y = -1, 0 # 진출 시작점을 (0, 0)으로 하기 위해서.
    k = 0
    m = 0 
    for i in range(n, 0, -1):
        for j in range(i):
            nx = x + steps[k][0]
            ny = y + steps[k][1]
            m += 1 # 한 번 진출할 때마다 1씩 올려줘서 순서대로 수가 리스트에 들어갈 수 있도록 한다.
            board[nx][ny] = m
            x = nx
            y = ny
        k += 1
        
    for i in board:
        answer.extend(i)
    return answer