11월 14일 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)[BOJ/18251]

포화 이진 트리의 직사각형 영역 내에서 노드들의 가중치 합이 최대가 되는 부분을 찾는 문제를 풀었다. 이 문제는 트리의 구조와 2차원 구간에서 최대 부분 합을 찾는 아이디어가 결합된 문제로, 동적 계획법(DP)과 DFS를 조합하여 해결할 수 있었다.

문제 접근 방법

1. 트리의 DFS 순회로 깊이와 인덱스 설정:

• 트리는 포화 이진 트리 구조를 가지고 있다. 따라서, 각 노드는 인덱스 규칙을 따르며, DFS로 순회하면서 각 노드의 깊이와 인덱스를 기록할 수 있다.
• 루트 노드부터 DFS를 통해 각 노드의 위치와 깊이를 저장하고, 이를 활용해 직사각형 영역을 계산하는 데 필요한 정보를 수집했다.

2. 노드의 가중치와 초기 최대값 설정:

• 입력받은 각 노드의 가중치를 저장하고, 트리의 모든 가중치가 음수인 경우 가장 큰 가중치 하나를 출력하면 되므로, 미리 모든 가중치의 최대값을 초기화했다.

3. 직사각형 내 최대 가중치 합 계산:

• 트리의 각 깊이 범위를 i에서 j로 설정하여 가능한 직사각형 영역을 지정한다.
• 지정한 깊이 범위 내에서 가중치 합을 최대화하는 연속 구간을 찾아야 하므로, 카데인 알고리즘(Kadane’s Algorithm)을 사용해 현재 범위에서 최대 부분합을 구했다.
• 이를 통해 모든 가능한 깊이 구간에서 최대 가중치 합을 찾아 최종 답을 도출했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static class Node {
        int depth;
        int index;
        long weight;

        public Node(int depth, int index, long weight) {
            this.depth = depth;
            this.index = index;
            this.weight = weight;
        }
    }

    static int n;
    static int pv = 0;
    static int[] id;
    static long[] weights;
    static ArrayList<Node> nodes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        id = new int[n + 1];
        weights = new long[n + 1];

        // 트리를 DFS로 순회하며 노드 깊이와 인덱스 기록
        dfs(1, 0);

        // 가중치 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        long initialMax = Long.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            long weight = Long.parseLong(st.nextToken());
            weights[id[i]] = weight;
            nodes.get(id[i]).weight = weight;
            initialMax = Math.max(initialMax, weight);
        }

        // 모든 가중치가 음수인 경우 가장 큰 값 하나를 출력
        if (initialMax <= 0) {
            System.out.println(initialMax);
            return;
        }

        long maxSum = 0;
        for (int i = 0; i < 20; i++) {
            for (int j = i; j < 20; j++) {
                long currentSum = 0, maxInRectangle = 0;
                for (Node node : nodes) {
                    if (node.depth < i || node.depth > j) continue;
                    currentSum = Math.max(0, currentSum + node.weight);
                    maxInRectangle = Math.max(maxInRectangle, currentSum);
                }
                maxSum = Math.max(maxSum, maxInRectangle);
            }
        }

        // 결과 출력
        System.out.println(maxSum);
    }

    // DFS로 트리 노드를 순회하며 노드 깊이와 인덱스 기록
    static void dfs(int node, int depth) {
        if (node > n) return;

        // 왼쪽 자식 노드 방문
        if (node * 2 <= n) dfs(node * 2, depth + 1);

        // 현재 노드 깊이와 인덱스 기록
        id[node] = pv;
        nodes.add(new Node(depth, pv++, 0));

        // 오른쪽 자식 노드 방문
        if (node * 2 + 1 <= n) dfs(node * 2 + 1, depth + 1);
    }
}

코드 설명

1. 노드 클래스 정의:

static class Node {
    int depth;
    int index;
    long weight;

    public Node(int depth, int index, long weight) {
        this.depth = depth;
        this.index = index;
        this.weight = weight;
    }
}

• Node 클래스는 각 노드의 깊이(depth), 인덱스(index), 가중치(weight)를 저장하는 역할을 한다.

2. DFS 순회를 통해 노드의 깊이와 인덱스 설정:

static void dfs(int node, int depth) {
    if (node > n) return;

    // 왼쪽 자식 노드 방문
    if (node * 2 <= n) dfs(node * 2, depth + 1);

    // 현재 노드 깊이와 인덱스 기록
    id[node] = pv;
    nodes.add(new Node(depth, pv++, 0));

    // 오른쪽 자식 노드 방문
    if (node * 2 + 1 <= n) dfs(node * 2 + 1, depth + 1);
}

• DFS 방식으로 트리를 순회하며 각 노드의 깊이와 인덱스를 설정한다.
• id 배열은 각 노드의 인덱스를 저장하고, nodes 리스트는 노드 객체들을 깊이 순서대로 저장한다.

3. 가중치 입력 및 초기 최대값 설정:

StringTokenizer st = new StringTokenizer(br.readLine());
long initialMax = Long.MIN_VALUE;
for (int i = 1; i <= n; i++) {
    long weight = Long.parseLong(st.nextToken());
    weights[id[i]] = weight;
    nodes.get(id[i]).weight = weight;
    initialMax = Math.max(initialMax, weight);
}

• 입력받은 가중치를 노드의 인덱스에 맞게 저장하고, 모든 가중치가 음수일 때를 대비하여 최대 가중치를 초기화한다.

4. 직사각형 영역 내 최대 가중치 합 계산:

long maxSum = 0;
for (int i = 0; i < 20; i++) {
    for (int j = i; j < 20; j++) {
        long currentSum = 0, maxInRectangle = 0;
        for (Node node : nodes) {
            if (node.depth < i || node.depth > j) continue;
            currentSum = Math.max(0, currentSum + node.weight);
            maxInRectangle = Math.max(maxInRectangle, currentSum);
        }
        maxSum = Math.max(maxSum, maxInRectangle);
    }
}

• 가능한 깊이 구간 i에서 j까지를 설정하고, 그 구간 내에서 최대 부분합을 구한다.
• 현재 깊이 범위에서 Kadane's Algorithm을 사용하여 최대 부분합을 찾아 maxSum을 업데이트한다.

So...

이 문제는 트리의 구조와 최대 부분합을 계산하는 방법을 결합해야 했다. 특히, 포화 이진 트리의 특성을 활용해 DFS를 통해 노드를 깊이별로 분류하고, 가능한 깊이 구간 내에서 직사각형 영역의 최대 가중치 합을 효율적으로 구하는 방식이 핵심이었다.