[프로그래머스] 삼각 달팽이 (C++)

삼각 달팽이 / Lv.2

---

문제  설명 )

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

 

 

 

 

제한 사항 )

• n은 1 이상 1,000 이하입니다.

 

 

 

입출력 예 )

 

 

입출력 예 설명 )

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

 

풀이)

위 배열을 2차원으로 생각하고, 왼쪽으로 밀어 다음과 같이 풀어주었다.

 

1
2	15
3	16	14
4	17	21	13
5	18	19	20	12
6	7	8	9	10	11

 

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<int>> vec;
 
int num;
int dx[] = {1, 0, -1};
int dy[] = {0, 1, -1};
 
void dfs(int x, int y, int idx)
{
    // 다음 칸 탐색 
    int nx = x + dx[idx];
    int ny = y + dy[idx];
    
    // 삼각형을 벗어나지 않고,
    // 이동할 다음 칸이 비어있다면 
    if(0 <= nx && nx < num
       && 0 <= ny && ny < num
       && !vec[nx][ny])
    {
        vec[nx][ny] = vec[x][y] + 1;
        dfs(nx, ny, idx);
    }
    else
    {
        // 방향을 전환하고
        if(idx == 0 || idx == 1) idx++;
        else idx = 0;
        
        // nx, ny를 다시 설정한다.
        nx = x + dx[idx];
        ny = y + dy[idx];
        
        // 앞으로 갈 곳이 이미 채워져 있다면 끝
        if(vec[nx][ny]) return;
        else
        {
            vec[nx][ny] = vec[x][y] + 1;
            dfs(nx, ny, idx);
        }
    }
}
 
 
vector<int> solution(int n) {
    vector<int> answer;
    
    num = n;
    vec.resize(n, vector<int>(n, 0));
    
    vec[0][0] = 1;
    dfs(0, 0, 0);
    
    for(auto ele: vec) for(auto e: ele)
    {
        if(e != 0)
        {
            answer.push_back(e);
        }
    }
    
    return answer;
}

---

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

프로그래머스