Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 배열 중첩(Array Nesting) 문제 풀이: DFS로 최장 순환 길이 구하기

문제 설명

길이가 N이고 인덱스가 0부터 시작하는 배열 A가 있다고 가정해 보겠습니다. 이 배열은 0부터 N-1까지의 모든 정수를 정확히 한 번씩 포함합니다. 우리가 구해야 하는 것은 다음 규칙을 따르는 집합 S의 최대 길이입니다.

S[i] = {A[i], A[A[i]], A[A[A[i]]], ...}

집합 S는 인덱스 i에서 시작하여 첫 원소로 A[i]를 선택하고, 그다음에는 A[A[i]], 그 뒤에는 A[A[A[i]]]를 차례로 추가합니다. 이 과정을 계속 반복하다가 S 안에 중복된 값이 나타나기 직전에 추가를 멈춥니다.

예시

배열이 A = [5,4,0,3,1,6,2]일 때 정답은 4입니다. 인덱스 0에서 시작하면 다음과 같은 흐름을 따릅니다.

  • A[0] = 5
  • A[5] = 6
  • A[6] = 2
  • A[2] = 0
  • 그다음 값은 A[0] = 5로 이미 집합에 존재하므로 탐색 종료

따라서 집합 S = {5, 6, 2, 0}의 길이인 4가 됩니다. 같은 방식으로 인덱스 1에서 시작하면 {4, 1}(길이 2), 인덱스 3에서 시작하면 {3}(길이 1)이 되므로, 전체 최댓값은 4입니다.

접근 방법: DFS 활용

이 문제는 본질적으로 각 인덱스에서 출발하는 순환(cycle)을 찾는 것과 같습니다. 깊이 우선 탐색(DFS)을 사용하면 효율적으로 해결할 수 있으며, 알고리즘 단계는 다음과 같습니다.

  1. dfs 함수 생성: node, arr 배열, 경로를 담을 v 배열, 방문 여부를 기록할 visited 집합을 매개변수로 받습니다.
  2. node가 이미 방문한 노드라면 즉시 반환합니다.
  3. node를 v에 삽입하고 visited에 방문 표시를 합니다.
  4. dfs(arr[node], arr, v, visited)를 재귀 호출합니다.
  5. 메인 로직: ret := 0, n := nums의 크기로 초기화하고 visited 집합을 만듭니다.
  6. i를 0부터 n-1까지 순회합니다.
    • 새로운 배열 v를 생성합니다.
    • nums[i]를 아직 방문하지 않았다면 dfs(nums[i], nums, v, visited)를 호출합니다.
    • ret을 ret과 v의 크기 중 더 큰 값으로 갱신합니다.
  7. 최종적으로 ret을 반환합니다.

한 번 방문한 노드는 다른 시작점에서 다시 탐색할 필요가 없습니다. 어느 지점에서 시작하든 결국 같은 순환에 속하기 때문입니다. visited 집합 덕분에 각 노드를 한 번씩만 확인하면 되므로, 전체 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)입니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   void dfs(int node, vector <int>& arr, vector <int>& v, set <int>& visited){
      if(visited.count(node)) return;
      v.push_back(node);
      visited.insert(node);
      dfs(arr[node], arr, v, visited);
   }
   int arrayNesting(vector<int>& nums) {
      int ret = 0;
      int n = nums.size();
      set <int> visited;
      for(int i = 0; i < n; i++){
         vector <int> v;
         if(!visited.count(nums[i]))dfs(nums[i], nums, v, visited);
         ret = max(ret, (int)v.size());
      }
      return ret;
   }
};
main(){
   vector<int> v = {5,4,0,3,1,6,2};
   Solution ob;
   cout << (ob.arrayNesting(v));
}

입력

[5,4,0,3,1,6,2]

출력

4

마무리

배열 중첩 문제는 배열의 값이 곧 다음 인덱스가 되는 특성 때문에 자연스럽게 순환 구조를 형성합니다. DFS와 방문 처리를 조합하면 모든 순환을 한 번씩만 확인하면 되므로 선형 시간 안에 답을 구할 수 있습니다. 재귀 호출이 부담스럽다면 명시적인 스택을 사용하는 반복형 DFS로도 동일하게 구현할 수 있으니 함께 연습해 보시기 바랍니다.