[C++] 3176번 도로 네트워크 - 자료 구조, 트리, 최소 공통 조상, 희소 배열

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define Vr first
#define R second

using namespace std;

const int MAX_TR = 20;
const int MAX_N = 100001;
const int INF = 987654321;

int N, K;
int DT[MAX_N];
int PA[MAX_N][MAX_TR];
int min_R[MAX_N][MAX_TR], max_R[MAX_N][MAX_TR];
pair<int, int> res;

vector<pair<int, int>> Vertex[MAX_N];

void dfs(int Pa, int no, int Depth, int len)
{
    DT[no] = Depth, PA[no][0] = Pa;
    min_R[no][0] = max_R[no][0] = len;
    
    FOR(i, 1, Vertex[no].size())
        if(Vertex[no][i-1].Vr!=Pa)
            dfs(no, Vertex[no][i-1].Vr, Depth+1, Vertex[no][i-1].R);
}

pair<int, int> dis(int a, int b)
{
    int Min=INF, Max=0;
    
    if(DT[a] != DT[b]) {
        if(DT[a] < DT[b]) swap(a, b);
        
        int dif = DT[a]-DT[b];
        
        for(int i=0; dif>0; i++) {
            if(dif%2) {  //Bit 계산
                Min = min(Min, min_R[a][i]);
                Max = max(Max, max_R[a][i]);
                a = PA[a][i];
            }
            dif = dif>>1;
        }
    }
    
    if(a != b) {
        for(int k=MAX_TR-1; k>=0; k--) {
            if(PA[a][k] && PA[b][k] && PA[a][k]!=PA[b][k]) {
                Min = min({Min, min_R[a][k], min_R[b][k]});
                Max = max({Max, max_R[a][k], max_R[b][k]});
                a = PA[a][k]; b=PA[b][k];
            }
        }
        Min = min({Min, min_R[a][0], min_R[b][0]});
        Max = max({Max, max_R[a][0], max_R[b][0]});
    }
    
    return {Min, Max};
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    FOR(i, 0, MAX_N-1) FOR(j, 0, MAX_TR) min_R[i][j]=INF;
    
    cin >> N;
    
    FOR(i, 1, N-1) {
        int a, b, r;
        cin >> a >> b >> r;
        
        Vertex[a].push_back({b, r});
        Vertex[b].push_back({a, r});
    }
    
    dfs(0, 1, 0, 0);
    
    FOR(k, 1, MAX_TR-1) {
        FOR(idx, 1, N) {
            if(PA[idx][k-1]) {
                PA[idx][k] = PA[ PA[idx][k-1] ][k-1];
                min_R[idx][k] = min(min_R[PA[idx][k-1]][k-1], min_R[idx][k-1]);
                max_R[idx][k] = max(max_R[PA[idx][k-1]][k-1], max_R[idx][k-1]);
            }
        }
    }
    
    cin >> K;
    while(K--) {
        int a, b; cin >> a >> b;
        res = dis(a, b);
        cout << res.Vr << ' ' << res.R << '\n';
    }
    
    return 0;
}

희소 배열이 처음 보는 알고리즘이라서 공부한다고 많이 힘들었다. 희소 배열 너무 어려워요...ㅜㅜ

 

아무리 봐도 이해되지가 않아서... 어쩔 수 없이, 다른 사람의 코드를 참고해서 코드를 작성했다. 물론 시간을 줄였다.

 

아 그리고 다른 사람 코드를 보던 중 굉장히 깔끔하게 쓰인 코드가 있어서 아래에 참조하였다.

 

 

 

 

 

<Sparse Table Algorithm 1>

https://hello-capo.netlify.app/algorithm-sparse-table/

🧩 [Algorithm] 희소 배열(Sparse Table) 알고리즘 | hello-capo!

 

<Sparse Table Algorithm 2>

https://tech-interview.tistory.com/175

[C++] 희소 테이블(Sparse Table)

 

<Sparse Table Algorithm 3>

https://jisungbin.medium.com/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-sparse-table-%ED%9D%AC%EC%86%8C-%EB%B0%B0%EC%97%B4-95dfaf0b8ddb

[자료구조] Sparse Table (희소 배열)

 

<참고한 코드>

https://everenew.tistory.com/96

[백준] No.3176 - 도로 네트워크 (C++, 최소 공통 조상)

 

<깔끔한 코드(풀어야 볼 수 있습니다)>

https://www.acmicpc.net/source/48942184

로그인

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.