[C++로 풀이] 삼각 달팽이 (DFS)⭐⭐

📌 삼각 달팽이

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

void DFS(vector<int>& answer, int& n, int elem, int startIndex, int depth) {

    int arrSize = n * (n + 1) / 2;

    // 1. 꼭짓점
    answer[startIndex] = elem++;

    if (elem > arrSize)
        return;

    const int length = n - 3 * depth;

    // 2. 왼쪽 빗변 
    int indexTerm = 2 * depth + 1;
    for (int count = 1; count <= length - 1 && elem <= arrSize; count++) {
        answer[startIndex + indexTerm] = elem++;
        startIndex += indexTerm;
        indexTerm++;
    }

    // 3. 밑변 
    for (int count = 1; count <= length - 1 && elem <= arrSize; count++) {
        startIndex++;
        answer[startIndex] = elem++;
    }

    // 4. 오른쪽 빗변 
    indexTerm =  n - depth;
    for (int count = 1; count <= length - 2 && elem <= arrSize; count++) {
        answer[startIndex - indexTerm] = elem++;
        startIndex -= indexTerm;
        indexTerm--;
    }

    int X = 2 * (depth + 1);
    startIndex = X * (X + 1) / 2 + (depth + 1);
    if (elem <= arrSize)
        DFS(answer, n, elem, startIndex, depth + 1);

    return;
}

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

    DFS(answer, n, 1, 0, 0);

    return answer;
}

근데 이거를 DFS로 풀이했다고 말할 수 있을지 잘 모르겠다.. 말할 수..있나? 😅 하나하나 다 깊이 들어가는식으로 방문한거니까 그렇다고 할 수 있겠G..?

재귀 사용하니까 오히려 너무 복잡했다.. 1 차원 배열 인덱스의 변화되는 규칙을 찾으려니 너무너무 복잡하고 힘들었다.. 😭

예를 들어 n이 7이라면 이렇게 3개의 삼각형이 생긴다고 보았다.

• depth = 0 일땐 노란색
• depth = 1 일땐 초록색
• depth = 2 일땐 파란색
  • 이렇게 하나밖에 없는건 length 가 0인 것으로 간주함

재귀적으로 이렇게 depth가 늘어날 수록 더 작은 삼각형으로 들어가게 됨.

length 는 n - 3 * depth 로 정의함. n = 7 에서의 가장 큰 삼각형(depth = 0)에서는 length가 7이고, 초록색 삼각형일 때는

• 1️⃣ 새로운 삼각형의 꼭짓점 방문 (startIndex)
  • 위에 위에 사진의 파란 삼각형처럼 하나밖에 없는 삼각형에 도달했을 경우 꼭짓점만 찍고 재귀가 종료될 수 있도록 종료 조건을 꼭짓점 찍은 후 추가

     int arrSize = n * (n + 1) / 2;
    
     // 1. 꼭짓점
     answer[startIndex] = elem++;
    
     if (elem > arrSize)
         return;
    

• 2️⃣ 왼쪽 빗변 (주황 화살표) 👉 length - 1 개
  • 꼭짓점 [0] (depth = 0) 삼각형의 주황 화살표에서의 인덱스 차이 : 0, 1(0 + 1), 3(0 + 1 + 2), 6(0 + 1 + 2 + 3), 10(0 + 1 + 2 + 3 + 4), …
  • 꼭짓점 [4] (depth = 1) 삼각형의 주황 화살표에서의 인덱스 차이 : 4, 7(4 + 3), 11(4 + 3 + 4), 16(4 + 3 + 4 + 5), …

  •   // 2. 왼쪽 빗변 
      int indexTerm = 2 * depth + 1;
      for (int count = 1; count <= length - 1 && elem <= arrSize; count++) {
      answer[startIndex + indexTerm] = elem++;
      startIndex += indexTerm;
      indexTerm++;
      }
    

• 2️⃣ 밑변 (노란 화살표) 👉 length - 1 개
  • 1 번 과정에서 끝낸 startIndex에서 1씩 더한 곳에 저장하면 된다. (수평 방향이므로)

    for (int count = 1; count <= length - 1 && elem <= arrSize; count++) {
        startIndex++;
        answer[startIndex] = elem++;
    }
    

• 3️⃣ 오른쪽 빗변 (초록 화살표) 👉 length - 2 개
  • 꼭짓점 [0] (depth = 0) 삼각형의 초록 화살표에서의 인덱스 차이 : 27, 20(27 - 7), 14(27 - 7 - 6), 9(27 - 7 - 6 - 5), 10(0 + 1 + 2 + 3 + 4), …
  • 꼭짓점 [4] (depth = 1) 삼각형의 초록 화살표에서의 인덱스 차이 : 19, 13(19 - 6), 8(19 - 6 - 5), 4(19- 6 - 5 - 4), …

    indexTerm =  n - depth;
    for (int count = 1; count <= length - 2 && elem <= arrSize; count++) {
        answer[startIndex - indexTerm] = elem++;
        startIndex -= indexTerm;
        indexTerm--;
    }
    

• 다음 재귀 삼각형의 꼭짓점 정하고 다음 삼각형으로 이동

    int X = 2 * (depth + 1);
    startIndex = X * (X + 1) / 2 + (depth + 1);
    if (elem <= arrSize)
        DFS(answer, n, elem, startIndex, depth + 1);
  

🚀 다른 풀이

출처 및 참고 : 얍문님 블로그

내 풀이처럼 1차원 배열 상에서의 인덱스간 규칙을 찾으려고 애쓰지 않고.. 삼각형의 각 자리들을 2차원 배열에 대응시켜 2차원 좌표를 사용한다.(정삼각형이 아닌 직각삼각형 모양이 되게끔 정도만) 나중에 이 2차원 배열에 정리한 것을 1차원 배열에 읽어오기만 하면 땡이다. 좋은 풀이이니 이 포스트를 다시 본다면 얍문님 블로그에 들어가서 풀이와 코드 자세히 다시금 확인해보자..

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기