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

✅ LV.3

📌 월간 코드챌린지 시즌1

✏️ 최종 솔루션

⭐️ DFS
1. 현재 숫자, 현재 좌표, 현재 방향을 이동하며 숫자 기록
2. 현재 방향으로 이동 가능한지 확인
1) 이동 가능하다면 이동할 위치에 다음 숫자 저장하고 현재 방향은 그대로, 다음 숫자는 갱신해서 DFS 이어서 하기
2) 현재 방향으로 이동할 수 없다면 다음 방향으로 이동한 위치에 다음 숫자 저장하고 방향과 다음 숫자를 갱신해서 DFS 이어서 진행
❗️ 현재 방향과 다음 방향을 모두 갈 수 없는 경우는 숫자를 모두 기록한 경우밖에 없음

📌 self feedback

answer을 1차원으로 return 해야해서 오히려 꼬아서 생각했던 것 같다
일단 2차원 배열에 저장한 뒤, 1차원으로 변환해주는 것이 관건이었음
어찌보면 단순 구현 문제라서 속도를 더 높일 필요가 있다
방문 가능 여부를 어디서 체킹해줘야할지가 너무 헷갈렸다

✏️ 최종 code

#include <iostream>
#include <vector>

using namespace std;

// 아래, 오른, 위
int dx[3]={1,0,-1};
int dy[3]={0,1,-1};
int visit[1001][1001];

int num;
void dfs(int cnt, int x, int y, int d) {
    if(cnt==num*(num+1)/2) return;
    // 현재 방향으로 이동 불가능
    int nx=x+dx[d];
    int ny=y+dy[d];

    if((nx<=0 || nx >num || ny<=0 || ny>nx) || visit[nx][ny]!=0){
        // 다른 방향으로 이동
        if(d<=1) {
            nx=x+dx[d+1];
            ny=y+dy[d+1];
            visit[nx][ny]=cnt+1;
            dfs(cnt+1,nx,ny,d+1);
        } 
        else {
            nx=x+dx[0];
            ny=y+dy[0];
            visit[nx][ny]=cnt+1;
            dfs(cnt+1,nx,ny,0);
        }
    } 
    else {
        // 현재 방향으로 이동 가능
        visit[nx][ny]=cnt+1;
        dfs(cnt+1,nx,ny,d);
    }
}

vector<int> solution(int n) {
    vector<int> answer(n*(n+1)/2,0);
    num=n;

    visit[1][1]=1;
    dfs(1,1,1,0);
    
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            answer[(i-1)*i/2+j-1]=visit[i][j];
        }
    }
    
    return answer;
}