2872. Maximum Number of K-Divisible Components

문제 링크


내 코드

Solution 참고..


Solution

Approach 1: Depth-First Search (DFS)

  • 155ms, 177.99MB
  • Complexity
    • Let nn be the number of nodes in the graph, and let mm be the number of edges in the graph.
    • Time Complexity: O(n+m)O(n + m)
    • Space Complexity: O(n+m)O(n + m)
class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>> &edges,
                                vector<int> &values, int k) {
        // Step 1: Create adjacency list from edges
        vector<int> adjList[n];
        for (auto edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            adjList[node1].push_back(node2);
            adjList[node2].push_back(node1);
        }
        // Step 2: Initialize component count
        int componentCount = 0;

        // Step 3: Start DFS traversal from node 0
        dfs(0, -1, adjList, values, k, componentCount);

        // Step 4: Return the total number of components
        return componentCount;
    }

private:
    int dfs(int currentNode, int parentNode, vector<int> adjList[],
            vector<int> &nodeValues, int k, int &componentCount) {
        // Step 1: Initialize sum for the current subtree
        int sum = 0;

        // Step 2: Traverse all neighbors
        for (auto neighborNode : adjList[currentNode]) {
            if (neighborNode != parentNode) {
                // Recursive call to process the subtree rooted at the neighbor
                sum += dfs(neighborNode, currentNode, adjList, nodeValues, k,
                           componentCount);
                sum %= k;  // Ensure the sum stays within bounds
            }
        }

        // Step 3: Add the value of the current node to the sum
        sum += nodeValues[currentNode];

        // Step 4: Check if the sum is divisible by k
        sum %= k;
        if (sum == 0) componentCount++;

        // Step 5: Return the computed sum for the current subtree
        return sum;
    }
};

GPT

아래 코드는 트리(Tree) 에서 노드를 루트(여기서는 0번 노드)로 잡고 DFS를 수행하면서, 각 서브트리(subtree)의 합이 (k)로 나누어떨어지는(즉, 합이 0 mod (k)) 경우를 찾아 그러한 서브트리의 개수(componentCount)를 세는 알고리즘입니다.

일반적으로 “최대 (k)-로 나누어떨어지는 컴포넌트 수”라고 하면,
트리의 간선들을 적절히 끊어서 얻을 수 있는 서로 겹치지 않는 (disjoint) 서브트리들의 수를 구하는 문제로 등장합니다.
그 경우에는 “서브트리가 0 mod (k)가 될 때마다 해당 서브트리를 잘라내고(parent에게 0을 반환)” 하는 로직을 자주 씁니다.

그러나 이 코드에서는 if (sum == 0) componentCount++ 후에도 sum을 그대로 리턴하여, 부모 서브트리에 합산이 이어집니다. 즉, 서브트리를 ‘분리(cut)’ 하지 않고도 0 mod (k)인 경우를 세고 있어, “서브트리가 서로 겹칠 수 있음”에 유의해야 합니다.
문제 의도나 요건에 따라 다르지만, 흔히 “Disjoint 서브트리 개수를 최대화”하는 접근이라면 sum == 0일 때 return 0;으로 부모와 끊어주곤 합니다.

아래에서는 주어진 코드 자체의 흐름에 초점을 맞추어 설명하겠습니다.

코드 구조

int maxKDivisibleComponents(int n, vector<vector<int>> &edges,
                            vector<int> &values, int k) {
    // 1. 인접 리스트(adjacency list) 생성
    vector<int> adjList[n];
    for (auto &edge : edges) {
        int node1 = edge[0];
        int node2 = edge[1];
        adjList[node1].push_back(node2);
        adjList[node2].push_back(node1);
    }

    // 2. 서브트리가 0 mod k가 될 때마다 +1 할 카운터
    int componentCount = 0;

    // 3. 루트(0번 노드)부터 DFS 시작
    dfs(0, -1, adjList, values, k, componentCount);

    // 4. 개수 반환
    return componentCount;
}

// DFS 함수
int dfs(int currentNode, int parentNode, vector<int> adjList[],
        vector<int> &nodeValues, int k, int &componentCount)
{
    // (1) 현재 노드를 루트로 하는 서브트리 합
    int sum = 0;

    // (2) 자식(인접) 노드 순회
    for (auto neighborNode : adjList[currentNode]) {
        if (neighborNode != parentNode) {
            // 자식 서브트리의 합을 구해 더함
            sum += dfs(neighborNode, currentNode, adjList, nodeValues, k, componentCount);
            sum %= k;  // 오버플로우 방지 및 모듈로 연산
        }
    }

    // (3) 현재 노드의 값 추가
    sum += nodeValues[currentNode];
    sum %= k;

    // (4) 만약 이 서브트리 합이 0 mod k라면 컴포넌트 1개 발견
    if (sum == 0) {
        componentCount++;
    }

    // (5) 부모에게 이 서브트리의 합을 반환
    return sum;
}

1. 인접 리스트 생성

  • edges에는 (node1, node2) 형태의 간선 정보가 주어지고, 이 정보를 통해 각 노드에 연결된 이웃 노드 목록을 adjList에 저장합니다.
  • 문제에서 n개의 노드가 0번부터 (n-1)번까지 있다고 가정.

2. DFS로 서브트리 합을 구해 나가며, 0 mod (k)인 것 카운트

  • componentCount는 서브트리 합이 (k)로 나누어떨어질 때마다 1씩 증가합니다.
  • dfs(0, -1, ...) 호출로 0번 노드를 루트 삼아 깊이 우선 탐색을 시작합니다.

(a) 자식 노드 처리

  • DFS는 후위 순회(post-order) 형태로 진행됩니다.
    • 즉, 자식 노드를 모두 방문(dfs)한 뒤에 자신의 nodeValue를 더합니다.
  • 각 자식 서브트리에서 돌려받은 합을 sum에 누적하며, 모듈로 (k) 연산(sum %= k)으로 합을 계속 (k) 범위 안에서 관리합니다.

(b) 현재 노드 값 추가 및 “0 mod (k) 여부” 확인

  • 자식 노드들을 모두 처리한 뒤, sum += nodeValues[currentNode]로 현재 노드의 값을 추가합니다.
  • sum %= k 후, sum == 0이라면 componentCount++
    • 이 시점에서 “currentNode를 루트로 하는 전체 서브트리”가 (k)로 나누어떨어진다는 의미입니다.

(c) 부모에게 sum 반환

  • 반환값 sum은 부모 노드의 DFS에서 “현재 노드(subtree) 전체를 합산”하는 데 쓰입니다.
  • 주의할 점: 만약 sum == 0이었던 경우에도, return sum;에서 sum을 그대로 반환합니다.
    • **“서브트리가 분리(cut)되지 않고, 부모 노드가 다시 이 합을 이어받는다”**는 것이 핵심입니다.
    • 이로 인해 부모 서브트리 역시 0 mod (k)가 될 수도 있고, 그러면 또 componentCount++가 됩니다.

핵심 동작 해설

  1. DFS(트리 구조) + 후위 순회

    • 각 노드의 자식(=인접한 노드 중 부모가 아닌 노드)을 모두 재귀적으로 처리한 뒤, 자신의 값을 더합니다.

  2. 모듈로 연산

    • 매번 sum에 대해 % k를 수행함으로써, 큰 수가 되는 것을 방지하고, “0 mod kk”인지를 쉽게 체크할 수 있습니다.

  3. sum == 0이면 componentCount 증가

    • 이 코드는 “서브트리가 kk로 나누어떨어질 때마다” 카운트하는 로직을 담고 있습니다.
    • 하지만 “트리를 쪼개서(disjoint 서브트리) 최대 몇 개를 만들 수 있는지” 와 같은 문제에서는, 보통 여기서 sum == 0일 때 서브트리를 잘라내기 위해 return 0;을 하기도 합니다.
    • 본 코드에서는 그런 ‘컷(cut)’ 로직 없이 단순히 0 mod kk인 서브트리의 개수를 세는 방식이므로, 부모 서브트리가 동일한 부분을 또 활용해 0 mod kk가 될 수도 있습니다.

예시 간단 시뮬레이션

가령,

  • 노드 수 n=5n=5, 간선이 {(0,1),(0,2),(1,3),(1,4)}\{(0,1), (0,2), (1,3), (1,4)\}인 형태를 생각해봅시다.
  • 각 노드의 값이 values = [2, 1, 3, 6, 4]라 하고, k=3k=3라고 합시다.

트리 구조(루트: 0):

      (0) val=2
      /    \
(1)val=1   (2)val=3
   /  \
 (3)6 (4)4

  1. DFS(0, -1) 시작

    • sum=0 (초기)
    • 자식: 1, 2 두 개

  2. DFS(1, 0)

    • sum=0
    • 자식: 3, 4
    • DFS(3,1)
      • 자식 없음 → sum=0 + nodeValues[3]=6
      • 6 % 3=0 → componentCount++ (1 증가)
      • return 0 (코드상은 return 6 % 3 = 0 이지만, 값은 0)
    • sum += 0, sum=0 (여전히 0)
    • DFS(4,1)
      • 자식 없음 → sum=0 + nodeValues[4]=4
      • 4 % 3=1 → sum=1, 1 != 0 → componentCount 증가는 없음
      • return 1
    • sum += 1 (이전 sum=0이었음), sum=1
    • 자기 노드(1) 값 1을 더함 → sum=2, 2 % 3=2
    • 2 != 0 → componentCount 변화 없음
    • return 2

  3. DFS(2, 0)

    • 자식 없음 → sum=0 + nodeValues[2]=3
    • 3 % 3=0 → componentCount++ (1 증가, 총 2가 됨)
    • return 0

  4. 루트(0)로 돌아와서:

    • 자식(1)로부터 2, 자식(2)로부터 0을 받아 합산 → sum=2
    • 현재 노드 0의 값=2 추가 → sum=4 → 4 % 3=1
    • 1 != 0 → componentCount 변화 없음
    • 최종 return 1

위 시뮬레이션에서,

  • 노드 3의 서브트리 값=6 → 0 mod 3 → componentCount=1
  • 노드 2의 서브트리 값=3 → 0 mod 3 → componentCount=2
  • 그 뒤 루트(0) 서브트리는 1 mod 3 → count 증가 없음
  • 최종 componentCount=2

이때 서브트리가 서로 겹칠 수 있는지를 따지지 않았기 때문에,

  • 노드 2 자체가 하나의 서브트리(0 mod 3)
  • 노드 3 자체가 하나의 서브트리(0 mod 3)
  • 만약 노드 134를 묶었을 때의 합(1+6+4=11)이 3으로 나누어떨어지는지 등은 별개의 문제(겹칠 수도 있음)입니다.

결론

  1. 트리 DFS로 각 노드를 루트로 하는 서브트리 합을 구하고, 그 합이 kk로 나누어떨어지는 경우마다 componentCount를 증가시킵니다.
  2. 이 코드는 ‘서브트리를 잘라내는(cut) 방식’ 은 사용하지 않아, 서로 다른 서브트리가 겹치는 경우도 함께 세게 됩니다.
  3. “서브트리를 실제로 분할(disjoint)해서 얻을 수 있는 최대 개수”를 구하는 문제에서는, 보통 if (sum == 0) { componentCount++; return 0; } else return sum;처럼 구현합니다.
    • 그럼 자식 서브트리가 0 mod (k)가 되는 순간, 부모와의 연결(간선)을 ‘끊었다’고 간주하고, 부모 합에는 0이 더해지므로 또 다른 독립 서브트리를 찾을 수 있게 됩니다.
  4. 반면 이 코드(질문에 주어진 형태)는 단순히 DFS 중 만나는 모든 “0 mod kk” 서브트리를 카운팅하는 방식이며, 그 결과가 꼭 “서로 겹치지 않는” 컴포넌트 수와 일치하지 않을 수 있다는 점에 주의해야 합니다.

요약하자면, 각 노드가 루트인 서브트리의 합을 모듈로 kk로 확인하고, 0이면 componentCount++ 하는 간단한 DFS 로직입니다.


Approach 2: Breadth-First Search (BFS)

  • 320ms, 266.42MB
  • Complexity
    • Let nn be the number of nodes in the graph, and let mm be the number of edges in the graph.
    • Time Complexity: O(n+m)O(n + m)
    • Space Complexity: O(n+m)O(n + m)
class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges,
                                vector<int>& values, int k) {
        // Base case: if there are less than 2 nodes, return 1
        if (n < 2) return 1;

        int componentCount = 0;
        unordered_map<int, unordered_set<int>> graph;

        // Step 1: Build the graph
        for (const auto& edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            graph[node1].insert(node2);
            graph[node2].insert(node1);
        }

        // Convert values to long long to prevent overflow
        vector<long long> longValues(values.begin(), values.end());

        // Step 2: Initialize the BFS queue with leaf nodes (nodes with only one
        // connection)
        queue<int> queue;
        for (const auto& [node, neighbors] : graph) {
            if (neighbors.size() == 1) {
                queue.push(node);
            }
        }

        // Step 3: Process nodes in BFS order
        while (!queue.empty()) {
            int currentNode = queue.front();
            queue.pop();

            // Find the neighbor node
            int neighborNode = -1;
            if (!graph[currentNode].empty()) {
                neighborNode = *graph[currentNode].begin();
            }

            if (neighborNode >= 0) {
                // Remove the edge between current and neighbor
                graph[neighborNode].erase(currentNode);
                graph[currentNode].erase(neighborNode);
            }

            // Check divisibility of the current node's value
            if (longValues[currentNode] % k == 0) {
                componentCount++;
            } else if (neighborNode >= 0) {
                // Add current node's value to the neighbor
                longValues[neighborNode] += longValues[currentNode];
            }

            // If the neighbor becomes a leaf node, add it to the queue
            if (neighborNode >= 0 && graph[neighborNode].size() == 1) {
                queue.push(neighborNode);
            }
        }

        return componentCount;
    }
};

GPT

아래 코드는 트리(Tree) 에서 노드들의 값을 더했을 때 kk로 나누어떨어지는(=0 mod kk) 서브트리를 최대 몇 개 만들 수 있는가를 구하는 전형적인 아이디어 중 하나입니다.

  • “트리”라는 전제: 입력 그래프가 nn개의 노드와 n−1n-1개의 엣지를 가지고 있으며 사이클이 없다고 가정(문제 설정에 따라).
  • 리프 노드(leaf node)부터 바깥에서 안쪽으로(바텀업) 차례로 병합해 가면서, “값의 합이 kk로 나누어떨어지면 그 덩어리를 하나의 컴포넌트(서브트리)로 분리하고 카운팅”하는 로직입니다.

아래에서는 코드의 흐름을 단계별로 살펴보겠습니다.

전체 코드 구조

int maxKDivisibleComponents(int n, vector<vector<int>>& edges,
                            vector<int>& values, int k) {
    // 1) n이 2 미만이면(노드가 하나뿐이면), 답은 1
    if (n < 2) return 1;

    // 최종적으로 갯수를 세어 반환할 변수
    int componentCount = 0;

    // 그래프 인접 리스트 (unordered_map<int, unordered_set<int>>)
    unordered_map<int, unordered_set<int>> graph;

    // 2) 간선 정보를 통해 그래프 구성
    for (const auto& edge : edges) {
        int node1 = edge[0], node2 = edge[1];
        graph[node1].insert(node2);
        graph[node2].insert(node1);
    }

    // values를 long long으로 변환 (오버플로우 방지)
    vector<long long> longValues(values.begin(), values.end());

    // 3) 리프 노드(연결된 간선이 1개뿐인 노드)를 큐에 삽입
    queue<int> queue;
    for (const auto& [node, neighbors] : graph) {
        if (neighbors.size() == 1) {
            queue.push(node);
        }
    }

    // 4) BFS로 리프부터 차례로 처리
    while (!queue.empty()) {
        int currentNode = queue.front();
        queue.pop();

        // currentNode의 이웃(부모) 찾기
        int neighborNode = -1;
        if (!graph[currentNode].empty()) {
            neighborNode = *graph[currentNode].begin();  
            // currentNode가 연결된 유일한 노드(리프이므로 1개뿐)
        }

        // 그래프에서 currentNode <-> neighborNode 간 연결 제거
        if (neighborNode >= 0) {
            graph[neighborNode].erase(currentNode);
            graph[currentNode].erase(neighborNode);
        }

        // 5) currentNode의 값이 k로 나누어떨어지는지 확인
        if (longValues[currentNode] % k == 0) {
            // 이 노드는 독립적으로 하나의 "k-로 나누어떨어지는 서브트리"를 형성
            componentCount++;
        } else if (neighborNode >= 0) {
            // 나누어떨어지지 않으면, 이 값을 neighborNode로 '합산'해서 이어줌
            longValues[neighborNode] += longValues[currentNode];
        }

        // neighborNode가 새로 '리프'가 됐다면 큐에 삽입
        if (neighborNode >= 0 && graph[neighborNode].size() == 1) {
            queue.push(neighborNode);
        }
    }

    return componentCount;
}

주요 아이디어: 리프 노드부터 BFS(또는 트리의 바닥에서 위로 합치기)

  1. 리프 노드 선정

    • 차수가 1(이웃이 1개)인 노드는 리프(leaf)입니다.
    • 초기 단계에서, 모든 리프 노드를 큐에 넣습니다.

  2. 리프 노드를 하나씩 처리

    • 큐에서 리프 노드를 꺼냅니다(currentNode).
    • currentNode에 연결된 유일한 이웃(사실상 부모 역할) neighborNode를 찾아,
      • 엣지를 그래프에서 제거(둘 사이의 연결을 끊는다).
      • 만약 currentNode의 값(longValues[currentNode])이 (k)로 나누어떨어지면(0 mod k),
        • 독립적인 컴포넌트로 분리 → componentCount++
        • 이 노드는 이제 “최종 소모”되었으므로, 더 이상 부모에게 값을 전달하지 않습니다.
      • 나누어떨어지지 않으면, 부모 노드의 값에 currentNode의 값을 합산합니다(“병합”).
        • 이걸 통해 “작은 서브트리”가 “부모 서브트리”에 흡수된다고 볼 수 있습니다.

  3. 다시 리프 갱신

    • 연결을 끊고 나면, neighborNode의 차수가 줄어 새로운 리프가 될 수 있습니다.
    • 만약 차수가 1이 되었다면 큐에 넣어, 차례대로 반복 처리합니다.

왜 이렇게 하면 “최대” 개수를 세게 되나?

  • 노드 하나(또는 작은 서브트리)에서 값의 합이 kk의 배수가 되면, “더 큰 덩어리로 합쳐지기 전에” 해당 서브트리를 바로 분리하여 컴포넌트로 카운팅할 수 있습니다.
  • 만약 배수가 아니라면, 부모 노드(또는 이웃 노드)와 합산해 다음 단계에 다시 시도할 수 있습니다.
  • 결과적으로, 가능한 한 일찍(leaf 단계에서) “나누어떨어지는 서브트리”가 있으면 곧바로 떼어내어 카운팅하기 때문에, 서브트리를 더 이상 괜히 키워서 배수를 놓치는 일이 없습니다.
    • 이는 그리디(Greedy)한 아이디어이면서, 트리 구조에서 리프부터 처리를 해 나갈 때 유효합니다.

동작 예시 간단 시뮬레이션

가령 노드가 5개, 간선은

0 - 1
1 - 2
2 - 3
2 - 4

이며, 각 노드의 값이 [2, 4, 3, 9, 6]이고 (k=3)이라고 해 봅시다.

  1. 그래프 구성 & 리프 찾기

    • 인접 리스트:
      • 0 → {1} (차수 1, 리프)
      • 1 → {0,2}
      • 2 → {1,3,4}
      • 3 → {2} (차수 1, 리프)
      • 4 → {2} (차수 1, 리프)
    • 초기에 리프: 0, 3, 4

  2. 리프 처리 순서 (예: 큐= [0, 3, 4])

    • 리프 0 처리

      • 이웃은 1
      • longValues[0] = 2, 2 % 3 != 0 → 분리 불가
      • 부모(1)에 2를 더해 줌 → longValues[1] = 4 + 2 = 6
      • 간선 제거(0-1), → 0은 이제 고립, 1의 차수는 1줄어 1 → {2} (차수 1이 됨)
      • 1을 큐에 추가(새 리프) → 큐=[3,4,1]

    • 리프 3 처리

      • 이웃은 2
      • longValues[3] = 9, 9 % 3=0 → 컴포넌트 하나 찾음 (componentCount=1)
      • 간선(3-2) 제거 → 3은 분리, 2 → {1,4} (차수 2)
      • 3은 “배수”로 떨어져서 사라짐, 2에는 합치지 않음
      • 큐=[4,1]

    • 리프 4 처리

      • 이웃은 2
      • longValues[4] = 6, 6 % 3=0 → 또 컴포넌트 하나 찾음 (componentCount=2)
      • 간선(4-2) 제거 → 4 분리, 2 → {1} (차수 1)
      • 큐=[1,2] (2도 새 리프가 됐으므로 추가)

    • 리프 1 처리

      • 이웃은 2
      • longValues[1] = 6, 6 % 3=0 → 컴포넌트 하나 (componentCount=3)
      • 간선(1-2) 제거 → 1 분리, 2 → {} (차수 0)
      • 큐=[2]

    • 리프 2 처리

      • 이웃 없음(차수 0, 사실상 고립)
      • longValues[2] = 3, 3 % 3=0 → 컴포넌트 하나 (componentCount=4)
      • 큐=[] 끝

최종 componentCount = 4.

이 예시에서 보면,

  • 리프(3)의 값=9 (3의 배수) → 바로 분리
  • 리프(4)의 값=6 (3의 배수) → 바로 분리
  • 리프(0)의 값=2 (3의 배수 아님) → 부모(1)에 더해져 1의 값이 6이 됨 → 나중에 1이 리프가 되어 6(3의 배수)으로 분리
  • 남은 2도 값=3으로 최종 분리

정리

  1. 리프에서 출발
    • 리프 노드가 자기가 들고 있는 값이 kk로 나누어떨어지면, 그대로 하나의 “독립 서브트리(컴포넌트)”가 되어 카운트하고 노드를 제거(그래프에서 분리)한다.
    • 아니면, 그 값을 부모에게 넘겨서(합산) 더 큰 서브트리를 만들어본다.
  2. 반복
    • 부모(혹은 이웃)의 차수가 1이 되어 리프가 되면, 다시 위 과정을 반복
    • 이렇게 진행하면, 서로 겹치지 않는 최대 개수의 “kk-배수 서브트리”를 얻을 수 있다.
  3. 구현 방식
    • BFS(또는 DFS) 방식으로 리프 노드를 “바닥부터” 올려보내며 처리
    • 각 노드는 최대 한 번 리프가 되어 큐에 들어가기 때문에, 전체 복잡도는 O(n)O(n).

이 로직 덕분에 트리 상의 노드 값을 “가능한 한 빨리(k로 나누어떨어지면 바로 분리)” 해서 최대한 많은 컴포넌트를 구할 수 있게 됩니다.

정리하자면, 이 코드는 트리에서 리프 노드부터 제거해 가면서, “리프 노드가 가진 값이 (k)의 배수이면 즉시 한 컴포넌트로 카운트”, 아니라면 부모에게 값을 합산하여 다음에 검사하도록 하는 그리디+바텀업 방법입니다.
이렇게 하면 서로 겹치지 않는 서브트리를 최대한 많이 구성할 수 있고, 최종적으로 그 개수를 componentCount에 누적하게 됩니다.


Approach 3: Topological Sort / Onion Sort

  • 110ms, 176.06MB
  • Complexity
    • Let nn be the number of nodes in the graph, and let mm be the number of edges in the graph.
    • Time Complexity: O(n+m)O(n + m)
    • Space Complexity: O(n+m)O(n + m)
class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges,
                                vector<int>& values, int k) {
        if (n < 2) return 1;

        int componentCount = 0;
        vector<vector<int>> graph(n);
        vector<int> inDegree(n, 0);

        // Build the graph and calculate in-degrees
        for (const auto& edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            graph[node1].push_back(node2);
            graph[node2].push_back(node1);
            inDegree[node1]++;
            inDegree[node2]++;
        }

        // Convert values to long long to prevent overflow
        vector<long long> longValues(values.begin(), values.end());

        // Initialize the queue with nodes having in-degree of 1 (leaf nodes)
        queue<int> queue;
        for (int node = 0; node < n; node++) {
            if (inDegree[node] == 1) {
                queue.push(node);
            }
        }

        while (!queue.empty()) {
            int currentNode = queue.front();
            queue.pop();
            inDegree[currentNode]--;

            long long addValue = 0;

            // Check if the current node's value is divisible by k
            if (longValues[currentNode] % k == 0) {
                componentCount++;
            } else {
                addValue = longValues[currentNode];
            }

            // Propagate the value to the neighbor nodes
            for (int neighborNode : graph[currentNode]) {
                if (inDegree[neighborNode] == 0) {
                    continue;
                }

                inDegree[neighborNode]--;
                longValues[neighborNode] += addValue;

                // If the neighbor node's in-degree becomes 1, add it to the
                // queue
                if (inDegree[neighborNode] == 1) {
                    queue.push(neighborNode);
                }
            }
        }

        return componentCount;
    }
};

GPT

아래 코드는 트리(Tree) 형태의 그래프에서, 노드별로 주어진 값을 kk로 나누어떨어지도록 만드는 서브트리를 최대 몇 개 뽑아낼 수 있는지를 구하는 전형적인 알고리즘 패턴 중 하나입니다.

  • 트리(무방향, n개의 노드, n-1개의 간선)
  • 각 노드에는 값이 있고, 이를 누적(합)했을 때 kk의 배수가 되면 독립적인 서브트리(컴포넌트)로 떼어낼 수 있다고 간주합니다.
  • 리프 노드(차수가 1인 노드) 부터 시작하여, “노드의 값이 kk의 배수이면 곧바로 컴포넌트로 분리하고 제거”, “아니면 부모(이웃)에게 값을 합쳐서 넘긴 뒤 제거” 하는 과정을 BFS(또는 위상 정렬과 유사한 방식) 로 반복하여 최대 개수를 구합니다.

코드 구조

int maxKDivisibleComponents(int n, vector<vector<int>>& edges,
                            vector<int>& values, int k) {
    // (1) 예외 처리: 노드가 1개 이하인 경우
    if (n < 2) return 1;

    int componentCount = 0;
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);

    // (2) 그래프 인접 리스트 및 inDegree(차수) 계산
    for (const auto& edge : edges) {
        int node1 = edge[0], node2 = edge[1];
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
        inDegree[node1]++;
        inDegree[node2]++;
    }

    // (3) 오버플로우 방지를 위해 long long으로 변환
    vector<long long> longValues(values.begin(), values.end());

    // (4) 차수가 1(리프)인 노드를 모두 큐에 넣음
    queue<int> queue;
    for (int node = 0; node < n; node++) {
        if (inDegree[node] == 1) {
            queue.push(node);
        }
    }

    // (5) BFS/위상정렬 방식으로 리프 노드부터 처리
    while (!queue.empty()) {
        int currentNode = queue.front();
        queue.pop();
        inDegree[currentNode]--;

        long long addValue = 0;  // 부모(이웃)에게 넘길 값

        // (a) 현재 노드 값이 k로 나누어떨어지면, 독립 컴포넌트로 카운팅
        if (longValues[currentNode] % k == 0) {
            componentCount++;
        }
        // (b) 나누어떨어지지 않으면, 그 값을 부모에게 넘겨서 합산
        else {
            addValue = longValues[currentNode];
        }

        // (c) 연결된 이웃 노드들의 inDegree 갱신 및 값 합산
        for (int neighborNode : graph[currentNode]) {
            if (inDegree[neighborNode] == 0) {
                // 이미 처리된(또는 차수가 0이 된) 노드는 무시
                continue;
            }

            // currentNode를 제거했으므로, neighborNode의 차수 감소
            inDegree[neighborNode]--;

            // currentNode가 남긴 값을 neighborNode에 더함
            longValues[neighborNode] += addValue;

            // neighborNode가 새롭게 리프 노드(차수=1)가 되면 큐에 삽입
            if (inDegree[neighborNode] == 1) {
                queue.push(neighborNode);
            }
        }
    }

    return componentCount;
}

동작 방식

  1. 그래프 및 차수(inDegree) 계산

    • graph[node]에 연결된 노드 목록을 저장하고, 각 노드의 차수(연결된 간선 수)를 inDegree[node]에 기록합니다.
    • 트리이므로 전체 간선은 n-1개입니다.

  2. 리프 노드(차수 1) 찾기

    • 처음에 차수가 1인 노드들을 큐에 넣습니다. (대표적인 “위상 정렬”에서의 시작 노드 찾기와 유사)

  3. BFS/위상 정렬 순회

    • 큐에서 currentNode를 꺼내 처리:
      1. currentNode의 값을 확인
      • 만약 longValues[currentNode] % k==0longValues[currentNode] \ \% \ k == 0이면,
        • “이 노드는 독립적인 하나의 서브트리”로 분리 가능 → componentCount++
        • 부모(이웃)에게 값을 더하지 않음 (이미 분리해서 제거했기 때문)
      • 아니면, 부모(이웃)에게 넘길 addValue를 설정(= longValues[currentNode]).
      1. currentNode와 이웃 노드 neighborNode 간의 간선을 effectively “제거”
      • inDegree[neighborNode]-- (연결이 끊겼으므로 차수 감소)
      • longValues[neighborNode] += addValue (나누어떨어지지 않은 값만 이웃에게 흡수)
      1. neighborNode의 차수가 1이 되면 새 리프 → 큐에 삽입
      • 이렇게 순차적으로 바깥(리프)에서부터 안쪽(부모)으로 값을 합쳐 나갑니다.

  4. 반복

    • 위 과정을 큐가 빌 때까지 반복하면, 최종적으로 “가능한 한 많은 서브트리” 가 k의 배수 형태로 분리되었을 때의 개수를 얻습니다.

왜 “최대 개수”가 보장될까?

  • 그리디 전략:

    • 리프 노드가 kk로 나누어떨어지면, 더 큰 서브트리에 포함시키지 않고 곧바로 떨어뜨려(카운트하고) 제거해 버립니다.
    • 만약 리프 노드가 배수가 아니라면, 그 값을 부모에게 “병합”하여 부모 쪽에서 다시 확인합니다.
    • 이렇게 리프부터 시작해 가능한 한 일찍 독립 컴포넌트를 만들어내는 것이, 트리에서 “서로 겹치지 않는” 서브트리들을 최대 개수로 얻는 방법과 일치합니다.

  • 예시

    1. 리프 노드 A의 값이 12, k=3k=3이라면, 바로 하나의 서브트리가 되어(또는 간선을 끊고) componentCount++.
    2. 리프 노드 B의 값이 5, k=3k=3라면, 5로는 나누어떨어지지 않으니 부모와 합산해보는 식입니다.
    • 이 과정을 모든 리프에 대해 반복하면, 중복 없이(disjoint) 서브트리가 만들어지므로 최대 개수 달성.

정리

  1. 트리 + 그리디 + 위상 정렬(BFS) 아이디어
    • 리프 노드부터 제거하면서, 값이 kk 배수면 곧바로 컴포넌트로 취급해 카운트.
    • 배수가 아니면 부모(이웃)에 값을 넘겨서 합산하고, 리프 노드는 제거.
  2. 이 과정을 반복
    • 이웃 노드의 차수가 1이 되면 새로운 리프가 되어, 같은 로직을 적용.
  3. 최종적으로 얻은 componentCount 가 서로 겹치지 않는 kk-배수 서브트리의 최대 개수가 됩니다.

코드에서 핵심은 in-degree(차수) 관리와 값 합산, 그리고 리프 노드 업데이트를 올바르게 수행하는 것이며, 이는 전체를 O(n)O(n) 시간 안에 처리할 수 있습니다.


Onion Sort

Onion Sort라는 것은 보통 정식으로 인정된(또는 널리 알려진) 표준 정렬 알고리즘은 아닙니다. 간혹 프로그래머나 커뮤니티에서 “농담(joke)” 혹은 “학습 자료 예시” 로 언급되는 경우가 있습니다. 주로 다음 두 가지 맥락에서 볼 수 있습니다:

  1. 농담 알고리즘(Joke Algorithm)

    • “양파를 까면 눈물이 나듯이, 이 정렬 알고리즘을 쓰면 코드를 짜는 사람이 혹은 컴퓨터가 고통받는다”라는 식의 유머로 만들어진 가상의 알고리즘입니다.
    • 실제로는 매우 비효율적이거나, 정확한 동작 원리가 없으며, 대개 Bubble Sort나 Bogo Sort 같은 정렬 중 하나를 변형·비꼬아 부르는 용도로 쓰이기도 합니다.

  2. 레이어(계층)를 차례차례 벗겨내듯 정렬한다는 비공식적 별칭

    • 간혹 “배열(리스트)의 ‘겉껍질(최댓값/최솟값)부터 하나씩 벗겨내며 정렬하는 방식’”이라는 식으로, 어떤 아이디어를 설명하기 위해 “Onion Sort”라는 이름을 장난스럽게 붙이는 경우가 있습니다.
    • 예: 최소값을 찾아 맨 앞에, 최대값을 찾아 맨 뒤에 두는 식으로 계속 겉에서부터 안쪽으로 정렬을 완성해가는 발상을 “양파 껍질 벗기기”에 비유할 수 있습니다.
    • 하지만 이 또한 공식적으로 정립된 알고리즘이라고 하기는 어렵고, 특정 구현 예시에서 붙여본 ‘닉네임’ 정도로 보는 편이 맞습니다.

결론

  • “Onion Sort”는 정식으로 정립되거나 널리 쓰이는 정렬 알고리즘이 아니라, 주로 농담 또는 비공식 아이디어로 언급되는 이름입니다.
  • 따라서 진지하게 “Onion Sort의 복잡도”나 “정확한 구현” 같은 것을 찾기보다는, 코드 유머나 학습 자료 안에서 가볍게 등장하는 개념 정도로 이해하시면 됩니다.