프로그래머스 - 삼각 달팽이(c++)

 처음보면 되게 난해할 수 있는 문제이다. 방법이 있긴한가 싶었다.

처음 생각한 풀이는 DP였다. 그러나 DP는 최적의 값을 찾는 것인데 단순 배열 채우기가 DP?는 아닐거라 생각했다. 그다음은 dfs였는데 하삼각행렬만 가능하다고 치고 방향을 계속 바꿔주면 될 것 같았다. 

이런 식으로 계속 규칙이 있음을 알 수 있다. 어차피 방향은 3가지뿐이라 재귀만 잘 따지면 가능할 것 같았다.

dir 이라는 방향을 저장해두는 변수를 하나 만들고 

dir = 0 이면 아래방향

dir = 1 이면 오른쪽

dir = 2 이면 왼쪽 대각선

으로 이동하게 만들고 각 방향마다 몇번 이동해야하는지 정해두었다.

그런데 그림으론 저렇지만 코딩을하고나니 첫번째때 0,0 에서 시작하니까 첫 아래방향에 cnt = n - 1 이 되는 것을 알 수 있었다. 좀 더 매끄럽게 짤 수도 있겠지만 그냥 첫번째 순회때만 유도리를 챙겼다. 그리고 짜고 나니 이건 그냥 구현일 뿐 dfs는 아니었다. 그냥 함수이름만 dfs

 

#include <string>
#include <vector>
#include <iostream>
#define MAX 1001
using namespace std;

int boad[MAX][MAX];

void dfs(int herex, int herey,int num ,int cnt, int dir, int limit, int check){
    if(cnt == limit){
        if(check == 1){
            if(dir == 1)
                limit--;
        }
        else
            limit--;
        
            if(dir == 2){
                dir = 0;
            }   else{
                dir++;
            }
            check = -1;
        cnt = 0;
    }
    
    boad[herex][herey] = num;
    int nextx, nexty;
    if(dir == 0){
        nextx = herex + 1;
        nexty = herey;
    }else if(dir == 1){
        nextx = herex;
        nexty = herey + 1;
    }else{
        nextx = herex - 1;
        nexty = herey - 1;
    }
    
    if(boad[nextx][nexty] != -1){
        return;
    }
    else dfs(nextx, nexty, num + 1, cnt + 1, dir, limit, check);
}

vector<int> solution(int n) {
    vector<int> answer;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            boad[i][j] = -1;
        }
    }
    dfs(0,0,1,0,0,n-1, 1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            if(boad[i][j] != -1)
                answer.push_back(boad[i][j]);
    }
    
    return answer;
}

 

흠... 난 분명 O(N) 이라 생각했는데 생각보다 시간이 오래걸렸다. 재귀 오버헤드 때문인가..?