Jerry Kim

42는 ‘The Hitchhiker’s Guide to the Galaxy’라는 SF 소설에서 삶, 우주, 그리고 모든 것에 대한 궁극적인 질문에 대한 해답이다.

9 minute read

N개의 도시와 그 도시들을 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시는 유일한 경로로 연결되어 있으며, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어질 때, 각 쌍에 대해 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성해야 한다. 이 문제는 트리 구조에서 두 노드 사이의 경로를 탐색하면서, 경로 상의 간선 가중치 중 최소값과 최대값을 빠르게 구하는 것이 핵심이다.

이를 위해 트리에서 두 노드의 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾는 알고리즘과 Sparse Table을 활용하여 쿼리를 효율적으로 처리해야 한다. Binary Lifting 기법을 사용하여 각 노드의 2^k번째 조상을 미리 계산해 두면, 두 노드의 LCA를 O(log N) 시간에 찾을 수 있다.

또한, 각 노드에서 조상 노드까지의 경로 상의 최소 및 최대 간선 가중치를 저장해 두면, 두 노드 사이의 경로에서 최소값과 최대값을 구하는 데에도 O(log N) 시간이 소요된다.

문제 : https://www.acmicpc.net/problem/3176
 

접근 방식

이 문제를 해결하기 위해 다음과 같은 알고리즘과 자료 구조를 사용하였다.

  1. 최소 공통 조상(LCA) 알고리즘: 트리에서 두 노드의 LCA를 찾기 위해 Binary Lifting 기법을 활용하였다. 이를 통해 두 노드의 LCA를 O(log N) 시간에 찾을 수 있다.

  2. Sparse Table: 각 노드의 2^k번째 조상을 미리 계산해 두는 테이블을 구축하였다. 또한, 각 노드에서 조상까지의 경로에서의 최소 및 최대 간선 가중치를 저장하여 쿼리를 효율적으로 처리하였다.

  3. DFS(Depth-First Search): 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록하였다.

  4. Binary Lifting: 각 노드의 2^k번째 조상을 빠르게 찾기 위해 Binary Lifting을 사용하였다.

이를 통해 각 쿼리에 대해 O(log N)의 시간 복잡도로 답을 구할 수 있으며, 전체 시간 복잡도는 O(N log N + K log N)이다.

C++ 코드와 설명

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100001;
const int MAXLOGN = 17; // 2^17 = 131072 > 1e5

int N;
vector<pair<int, int>> adj[MAXN]; // 인접 리스트: (연결된 도시, 도로의 길이)

int depth[MAXN]; // 각 도시의 깊이
int anc[MAXN][MAXLOGN + 1]; // anc[v][k]: 도시 v의 2^k번째 조상
int min_t[MAXN][MAXLOGN + 1]; // min_t[v][k]: 도시 v에서 anc[v][k]까지의 최소 도로 길이
int max_t[MAXN][MAXLOGN + 1]; // max_t[v][k]: 도시 v에서 anc[v][k]까지의 최대 도로 길이

void dfs(int u, int p) {
    for (auto &edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v != p) {
            depth[v] = depth[u] + 1; // 깊이 설정
            anc[v][0] = u; // 부모 설정
            min_t[v][0] = w; // 최소값 초기화
            max_t[v][0] = w; // 최대값 초기화
            dfs(v, u); // 재귀 호출
        }
    }
}

int main() {
    scanf("%d", &N);
    // 도로 정보 입력
    for (int i = 0; i < N - 1; ++i) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        adj[A].push_back({B, C});
        adj[B].push_back({A, C});
    }
    // 초기화
    memset(anc, -1, sizeof(anc));
    memset(min_t, 0x3f, sizeof(min_t)); // 매우 큰 값으로 초기화
    memset(max_t, 0, sizeof(max_t));    // 0으로 초기화

    // 루트 노드 설정
    depth[1] = 0;
    anc[1][0] = -1;

    // DFS를 이용해 깊이와 1번째 조상, 최소/최대 도로 길이 설정
    dfs(1, -1);

    // Sparse Table 구성
    for (int k = 1; k <= MAXLOGN; ++k) {
        for (int v = 1; v <= N; ++v) {
            if (anc[v][k - 1] != -1) {
                int mid_anc = anc[v][k - 1];
                anc[v][k] = anc[mid_anc][k - 1]; // 2^k번째 조상 설정
                min_t[v][k] = min(min_t[v][k - 1], min_t[mid_anc][k - 1]); // 최소값 갱신
                max_t[v][k] = max(max_t[v][k - 1], max_t[mid_anc][k - 1]); // 최대값 갱신
            }
        }
    }

    // 쿼리 처리
    int K;
    scanf("%d", &K);
    for (int i = 0; i < K; ++i) {
        int D, E;
        scanf("%d %d", &D, &E);
        int min_ans = 1e9 + 1;
        int max_ans = -1;

        if (depth[D] < depth[E])
            swap(D, E);

        // 깊이를 동일하게 조정
        for (int k = MAXLOGN; k >= 0; --k) {
            if (anc[D][k] != -1 && depth[anc[D][k]] >= depth[E]) {
                min_ans = min(min_ans, min_t[D][k]); // 최소값 갱신
                max_ans = max(max_ans, max_t[D][k]); // 최대값 갱신
                D = anc[D][k]; // 조상으로 이동
            }
        }

        if (D == E) {
            printf("%d %d\n", min_ans, max_ans);
            continue;
        }

        // LCA 찾기
        for (int k = MAXLOGN; k >= 0; --k) {
            if (anc[D][k] != -1 && anc[D][k] != anc[E][k]) {
                min_ans = min(min_ans, min_t[D][k]);
                min_ans = min(min_ans, min_t[E][k]); // 최소값 갱신
                max_ans = max(max_ans, max_t[D][k]);
                max_ans = max(max_ans, max_t[E][k]); // 최대값 갱신
                D = anc[D][k]; // 조상으로 이동
                E = anc[E][k]; // 조상으로 이동
            }
        }

        // LCA의 바로 아래 간선 처리
        min_ans = min(min_ans, min_t[D][0]);
        min_ans = min(min_ans, min_t[E][0]); // 최소값 갱신
        max_ans = max(max_ans, max_t[D][0]);
        max_ans = max(max_ans, max_t[E][0]); // 최대값 갱신

        printf("%d %d\n", min_ans, max_ans);
    }

    return 0;
}

코드 설명

  • 데이터 입력 및 초기화:
    • 도로 정보를 입력받아 인접 리스트 adj에 저장한다.
    • memset 함수를 사용하여 배열을 초기화한다.
      • anc 배열을 -1로 초기화하여 초기 상태를 설정한다.
      • min_t 배열은 큰 값으로, max_t 배열은 0으로 초기화한다.
  • DFS를 통한 깊이 및 조상 설정:
    • dfs 함수에서 각 노드의 깊이와 부모를 설정하고, 간선의 가중치를 min_t와 max_t에 저장한다.
    • 재귀적으로 트리를 탐색하며 정보를 수집한다.
  • Sparse Table 구축:
    • 이중 반복문을 통해 각 노드의 2^k번째 조상을 계산하고, 해당 경로에서의 최소 및 최대 간선 가중치를 갱신한다.
    • anc[v][k], min_t[v][k], max_t[v][k]를 업데이트한다.
  • 쿼리 처리:
    • 입력받은 두 노드의 깊이를 맞추기 위해 깊이가 더 깊은 노드를 위로 올린다.
    • 깊이를 맞춘 후, 두 노드가 같아질 때까지 k를 감소시키며 조상을 찾아간다.
    • 이 과정에서 최소값과 최대값을 갱신한다.
    • 최종적으로 LCA의 바로 아래 간선까지 고려하여 결과를 출력한다.

위의 코드는 컴파일 에러 없이 동작하며, 주어진 입력에 대해 올바른 출력을 생성합니다.

C++ without library 코드와 설명

stdio.h와 malloc.h만을 사용하여 표준 라이브러리를 사용하지 않고 구현한 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100001
#define MAXLOGN 17

typedef struct Edge {
    int to;
    int weight;
    struct Edge* next;
} Edge;

Edge* adj[MAXN]; // 인접 리스트
int depth[MAXN];
int anc[MAXN][MAXLOGN + 1];
int min_t[MAXN][MAXLOGN + 1];
int max_t[MAXN][MAXLOGN + 1];

void add_edge(int from, int to, int weight) {
    Edge* edge = (Edge*)malloc(sizeof(Edge));
    edge->to = to;
    edge->weight = weight;
    edge->next = adj[from];
    adj[from] = edge;
}

void dfs(int u, int p) {
    Edge* edge = adj[u];
    while (edge != NULL) {
        int v = edge->to;
        int w = edge->weight;
        if (v != p) {
            depth[v] = depth[u] + 1;
            anc[v][0] = u;
            min_t[v][0] = w;
            max_t[v][0] = w;
            dfs(v, u);
        }
        edge = edge->next;
    }
}

int main() {
    int N;
    scanf("%d", &N);

    // 도로 정보 입력
    for (int i = 0; i < N - 1; ++i) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        add_edge(A, B, C);
        add_edge(B, A, C);
    }

    // 초기화
    for (int i = 1; i <= N; ++i) {
        for (int k = 0; k <= MAXLOGN; ++k) {
            anc[i][k] = -1;
            min_t[i][k] = 1e9 + 1;
            max_t[i][k] = 0;
        }
    }

    // 루트 노드 설정
    depth[1] = 0;
    anc[1][0] = -1;

    // DFS를 이용해 깊이와 1번째 조상, 최소/최대 도로 길이 설정
    dfs(1, -1);

    // Sparse Table 구성
    for (int k = 1; k <= MAXLOGN; ++k) {
        for (int v = 1; v <= N; ++v) {
            if (anc[v][k - 1] != -1) {
                int mid_anc = anc[v][k - 1];
                anc[v][k] = anc[mid_anc][k - 1];
                if (anc[v][k] != -1) {
                    // 최소값 갱신
                    if (min_t[v][k - 1] < min_t[mid_anc][k - 1])
                        min_t[v][k] = min_t[v][k - 1];
                    else
                        min_t[v][k] = min_t[mid_anc][k - 1];
                    // 최대값 갱신
                    if (max_t[v][k - 1] > max_t[mid_anc][k - 1])
                        max_t[v][k] = max_t[v][k - 1];
                    else
                        max_t[v][k] = max_t[mid_anc][k - 1];
                }
            }
        }
    }

    // 쿼리 처리
    int K;
    scanf("%d", &K);
    for (int i = 0; i < K; ++i) {
        int D, E;
        scanf("%d %d", &D, &E);
        int min_ans = 1e9 + 1;
        int max_ans = 0;

        if (depth[D] < depth[E]) {
            int temp = D;
            D = E;
            E = temp;
        }

        // 깊이를 동일하게 조정
        for (int k = MAXLOGN; k >= 0; --k) {
            if (anc[D][k] != -1 && depth[anc[D][k]] >= depth[E]) {
                if (min_t[D][k] < min_ans)
                    min_ans = min_t[D][k];
                if (max_t[D][k] > max_ans)
                    max_ans = max_t[D][k];
                D = anc[D][k];
            }
        }

        if (D == E) {
            printf("%d %d\n", min_ans, max_ans);
            continue;
        }

        // LCA 찾기
        for (int k = MAXLOGN; k >= 0; --k) {
            if (anc[D][k] != -1 && anc[D][k] != anc[E][k]) {
                if (min_t[D][k] < min_ans)
                    min_ans = min_t[D][k];
                if (min_t[E][k] < min_ans)
                    min_ans = min_t[E][k];
                if (max_t[D][k] > max_ans)
                    max_ans = max_t[D][k];
                if (max_t[E][k] > max_ans)
                    max_ans = max_t[E][k];
                D = anc[D][k];
                E = anc[E][k];
            }
        }

        // LCA의 바로 아래 간선 처리
        if (min_t[D][0] < min_ans)
            min_ans = min_t[D][0];
        if (min_t[E][0] < min_ans)
            min_ans = min_t[E][0];
        if (max_t[D][0] > max_ans)
            max_ans = max_t[D][0];
        if (max_t[E][0] > max_ans)
            max_ans = max_t[E][0];

        printf("%d %d\n", min_ans, max_ans);
    }

    return 0;
}

코드 설명

  • 인접 리스트 구현:
    • 표준 라이브러리를 사용할 수 없으므로, Edge 구조체와 연결 리스트를 사용하여 인접 리스트를 구현하였다.
    • add_edge 함수를 통해 간선을 추가한다.
  • DFS 구현:
    • dfs 함수에서 재귀적으로 트리를 탐색하며 깊이와 조상을 설정하고, 간선 가중치를 저장한다.
  • Sparse Table 구축 및 쿼리 처리:
    • 최소값과 최대값을 갱신할 때 표준 라이브러리의 min, max 함수를 사용할 수 없으므로, 조건문을 사용하여 직접 구현하였다.
    • 쿼리 처리 로직은 앞서 설명한 것과 동일하다.

결론

이 문제는 트리에서 두 노드 사이의 경로에서 최소 및 최대 간선 가중치를 빠르게 구해야 하는 전형적인 LCA 응용 문제이다. Binary Lifting과 Sparse Table을 사용하여 각 노드의 조상 정보를 미리 계산해 두면, 쿼리를 O(log N)에 처리할 수 있다.

이를 통해 시간 복잡도를 효율적으로 관리하여 큰 입력에서도 빠르게 답을 구할 수 있었다. 또한, C++ 표준 라이브러리를 사용하지 않고도 알고리즘을 구현하여 언어의 기본 기능만으로도 충분히 문제를 해결할 수 있음을 확인하였다.

추가적으로, 이와 유사한 유형의 문제를 많이 풀어봄으로써 트리에 대한 이해와 알고리즘 구현 능력을 향상시킬 수 있을 것이다. 최적화 측면에서는 메모리 사용량을 줄이거나 더 효율적인 자료 구조를 활용하는 방안을 고려해 볼 수 있다.

Tags: , , , , , ,

Categories:

Source File: 2024-09-23-BOJ-3176.md

Updated:

Comments

You May Also Enjoy

[Algorithm] C++/Python 백준 5670번 : 휴대폰 자판

8 minute read

휴대폰에서 영단어를 입력할 때 버튼을 누르는 횟수를 최소화하기 위해 자동완성 기능을 활용하는 문제이다. 이 문제는 Trie(트라이) 자료 구조 또는 재귀적인 접근 방식을 사용하여 효율적으로 해결할 수 있다.

[Algorithm] C++/Python 백준 3679번 : 단순 다각형

6 minute read

이번 글에서는 주어진 점들로 자기 교차 없이 단순 다각형을 구성하는 문제인 백준 3679번 “단순 다각형”을 소개하고, 이를 해결하기 위한 접근 방식과 구현 방법을 살펴보겠다. 이 문제는 기하학적 알고리즘과 정렬을 활용하여 해결할 수 있으며, 효율적인 구현이 요구된다.

[Algorithm] C++/Python 백준 3653번 : 영화 수집

3 minute read

상근이는 영화 DVD를 수집하는 열성적인 수집가이다. 그는 자신의 DVD 콜렉션을 탑처럼 쌓아 보관한다. 영화를 보고 싶을 때마다 DVD의 위치를 찾아서, 쌓여 있는 콜렉션이 무너지지 않도록 조심스럽게 해당 DVD를 꺼낸다. 영화를 다 본 후에는 그 DVD를 가장 위에 놓는다.

[Algorithm] C++/Python 백준 2618번 : 경찰차

8 minute read

경찰차들은 도시의 여러 사건을 처리하기 위해 최적의 경로를 찾아야 한다. 이때 두 대의 경찰차가 이동한 거리의 합을 최소화하는 것이 목표이다. 도시의 구조와 사건의 발생 위치가 주어졌을 때, 어떻게 하면 두 경찰차의 총 이동 거리를 최소화할 수 있을까?