[프로그래머스] 삼각 달팽이 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

 

풀이 방법

n이 3일때를 예를 들어보겠다.

0 0 0

0 0 0

0 0 0

피라미드를 위와 같은 NxN 정사각형으로 생각해보자.

 

1 0 0

2 6 0

3 4 5

위와 같은 모양으로 만들 수 있다.

차례대로 위에서 읽으면 1, 2, 6, 3, 4, 5와 같이 피라미드 순서가 된다.

 

어떻게 NxN 정사각형인 2차원 배열을 채울 수 있을까?

채우는 방향은 3가지로 나뉜다.

1. 아래로 쭉 내려가기

2. 오른쪽으로 쭉 이동하기

3. 좌상단 대각선 방향으로 쭉 이동하기

이동할때 배열의 끝을 만나거나 0이 아닌 값을 만나게 된다면 방향을 틀면된다.

방향은 1 -> 2 -> 3 순으로 반복되며 3에서 방향을 틀면 1이 된다.

이렇게 이동시키면 되는데 더이상 다음 방향으로 이동이 불가능할때까지 반복하면 된다.

 

다른 사람들 풀이 방법을 봤는데

나처럼 상황에 맞춰 로직을 수행하는것이아닌 수학적인?? 방법으로 푼 방법이 간단하여

전체 코드에 주석은 달지않고 다른 방법을 소개하고자 한다.

 

쉬운 방법

N일때

처음 N칸 이동, 다음은 N-1칸 이동, N-2칸, ..., 1칸 이동한다.

규칙이 있었다.

이렇게 움직일 거리를 생각하며 아래로, 우측으로, 좌상단 대각선으로 이동을 반복하여 NxN배열을 채우면된다.

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

void recursion(int (&arr)[1000][1000],int x, int y, int num, int dir, int n) {
    
    arr[y][x]=num;
    if(dir==0) {
        if(y+1<n&&arr[y+1][x]==0)
            recursion(arr,x,y+1,num+1,0,n);
        else if(x+1<n&&arr[y][x+1]==0&&
                (y+1<n&&arr[y+1][x]!=0)||(y+1==n)) // 범위를 벗어나 (옆으로 이동할 수 있다) / 범위를 벗어나지 않으나 아래에 등록된 수가 있고 (옆으로 이동할 수 있음)
            recursion(arr,x+1,y,num+1,1,n);
        else
            return;
    } else if(dir==1) {
        if(x+1<n&&arr[y][x+1]==0) {
            recursion(arr,x+1,y,num+1,1,n);
        }
        else if((x-1>=0&&y-1>=0&&arr[y-1][x-1]==0)&&(
               (x+1<n&&arr[y][x+1]!=0)||(x+1==n))) {
            recursion(arr,x-1,y-1,num+1,2,n);
        }
        else
            return;
    } else {
        if(x-1>=0&&y-1>=0&&arr[y-1][x-1]==0)
            recursion(arr,x-1,y-1,num+1,2,n);
        else if((y+1<n&&arr[y+1][x]==0)&&
                (y+1<n&&arr[y-1][x-1]!=0))
            recursion(arr,x,y+1,num+1,0,n);
        else
            return;
    }
}

vector<int> solution(int n) {
    vector<int> answer;
    int arr[1000][1000];
    fill(&arr[0][0], &arr[999][1000], 0);
    recursion(arr, 0, 0, 1, 0, n);
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(arr[i][j]==0)
                break;
            answer.push_back(arr[i][j]);
        }
    }
    return answer;
}