이전에 풀었던 RGB 거리와 유사한 방식으로 풀었다.

최적의 값 dp[t]를 dp[t-1]을 통해서 구할 수 있으려면

t일 때의 최솟값 dp[t] 뿐만 아니라 왼발과 오른발의 위치 또한 계산에 포함되어야 하므로,

(dp[t-1]의 최솟값을 만족했던 왼발과 오른발의 위치가 dp[t]의 시점에서는 t-1의 해당 위치가 최적이 아닐 수 있기 때문)

t일 때의 왼발과 오른발의 모든 조합에서의 최솟값 dp[t]를 별도로 계산을 해야 한다.

편의를 위해 unordered_map을 사용했지만, 얼마든지 더 단순한 컨테이너를 사용할 수도 있을 것이다. 

공유할 정도로 이쁜 코드는 아니지만, 기록의 목적으로 남겨본다.

먼저 현재 발의 위치에서 옮기려는 위치 까지의 비용을 계산해주는 함수를 작성했다.

enum FootPos {
	CENTER = 0,
	UP,
	LEFT,
	DOWN,
	RIGHT
};

int calcEnergy(const int& target, FootPos prev_position) {
	FootPos target_position = (FootPos)target;

	if (target_position == prev_position) return 1;
	else if (prev_position == FootPos::CENTER)
		return 2;
	else if ((prev_position == FootPos::LEFT && target_position == FootPos::RIGHT) ||
		(prev_position == FootPos::RIGHT && target_position == FootPos::LEFT) ||
		(prev_position == FootPos::UP && target_position == FootPos::DOWN) ||
		(prev_position == FootPos::DOWN && target_position == FootPos::UP))
		return 4;
	else
		return 3;
}

후에 dp[0]에서의 최적값은 왼발 혹은 오른발을 order[0]의 위치로 옮긴 경우가 유일하므로 수동으로 값을 대입해주고,

dp[1] 이후의 값은 dp[0]일때와 유사하게

dp[t-1]에 존재하는 왼발과 오른발의 조합에서 왼발을 기존 위치에서 order[t]의 위치로 옮길 때

calcEnergy가 최소가 되는 값을 구해서 dp[t]의 값을 갱신해주는 방법으로 구현했다.

vector<unordered_map <int, int >> dp(order.size());
dp[0][order[0] * 5] = calcEnergy(order[0], FootPos::CENTER);
dp[0][order[0]] = calcEnergy(order[0], FootPos::CENTER);
for (int t = 1; t < order.size(); t++) {
    int min = -1;
    auto LEFT = (FootPos)(order[t]);
    for (int footpos = 0; footpos < 5; footpos++) {
        auto RIGHT = (FootPos)footpos;
        if (LEFT == RIGHT) continue;

        int min = -1;
        for (int prevpos = 0; prevpos < 5; prevpos++) {
            auto prevLEFT = (FootPos)prevpos;
            if (dp[t - 1].count(prevLEFT * 5 + RIGHT) == 0) continue;
            auto cost = dp[t - 1][prevLEFT * 5 + RIGHT] + calcEnergy(LEFT, prevLEFT);
            if (min == -1 || min > cost)
                min = cost;
        }
        if (min != -1)
            dp[t][LEFT * 5 + RIGHT] = min;
    }

    auto RIGHT = (FootPos)(order[t]);
    for (int footpos = 0; footpos < 5; footpos++) {
        auto LEFT = (FootPos)footpos;
        if (LEFT == RIGHT) continue;

        int min = -1;
        for (int prevpos = 0; prevpos < 5; prevpos++) {
            auto prevRIGHT = (FootPos)prevpos;
            if (dp[t - 1].count(LEFT * 5 + prevRIGHT) == 0) continue;
            auto cost = dp[t - 1][LEFT * 5 + prevRIGHT] + calcEnergy(RIGHT, prevRIGHT);
            if (min == -1 || min > cost)
                min = cost;
        }
        if (min != -1)
            dp[t][LEFT * 5 + RIGHT] = min;
    }
}

이번에도 집중의 문제로 구현이 까다로워서 시간이 조금 걸렸다.

비교적 간단한 문제였는데 빨리 풀지 못해서 아쉬웠다.

솔직히 말하면 수학 문제라 알고리즘 분류를 눌러서 문제를 살짝 컨닝했다.

근데 모든 수가 1부터 1000000 사이고, 겹치지 않는다는 점에서 약간의 실마리를 얻기는 했었다.

시간복잡도를 어림으로 계산 후 단순 최소공배수를 구하듯이 구현하면 됐다.

1000000정도는 배열로 담을 수 있기 때문에, 배열을 무식하게 사용하지만 가장 빠르게 구현했다.

유의할 점은, 인덱스를 담았기 때문에, 해당 인덱스를 담은 배열을 0으로 초기화하면 안된다는 점이다.

처음에 틀려서 고민하다 챗 지피티한테 물어봤는데 바로 알려줘서 허탈했다.

사실 이런 사소한 이슈들이 현실에선 하루종일 고민하기도 하는 것이라, 실제 문제의 경중과는 다르게

신중하게 생각하는 버릇을 들여야 이런 실수를 방지할 수 있다.

vector<int> card(N);

int max = 0;

for (int i = 0; i < N; i++) {
    cin >> card[i];
    num[card[i]] = i+1;
    if(max < card[i])
        max = card[i];
}

vector<int> score(N, 0);
for (int i = 0; i < N; i++) {
    auto item = card[i];
    for (int j = 2; item * j <= max; j++) {
        if (num[item * j] != 0) {
            score[i]+=1;
            score[num[item*j]-1]-=1;
        }
    }
}

알고리즘이 문제에 그대로 노출되어 있는 기본적인 문제이다.

이 개념의 응용 문제도 골드4였는데, 난이도가 동일한 걸 보니

새삼 문제의 난이도는 절대적인 수치와는 거리가 멀다는 것을 느꼈다.

Union-Find 개념을 복습할 수 있는 좋은 문제였다.

class UnionFind {
	vector<int> parent;
	vector<int> rank;
	public:
	UnionFind(int n) {
		parent.resize(n);
		rank.resize(n,1);
		for(int i = 0 ; i < n ; i++)
			parent[i] = i;
	}
	int findParent(int cur) {
		if(parent[cur] != cur)
			parent[cur] = findParent(parent[cur]);

		return parent[cur];
	}
	bool insert(const int& a, const int& b) {
		auto a_root = findParent(a);
		auto b_root = findParent(b);
		if(a_root == b_root) return false;
		if (rank[a_root] > rank[b_root]) {
			parent[b_root] = a_root;
		}
		else if (rank[a_root] < rank[b_root]) {
			parent[a_root] = b_root;
		}
		else {
			parent[b_root] = a_root;
			rank[a_root] += 1;
		}
		return true;
	}
};

int main() {
	int N,M, i = 0;
	cin >> N >> M;
	UnionFind uf(N);
	for (i = 0; i < M; i++) {
		int a, b;
	 	cin >> a >> b;
		if(!uf.insert(a,b)) break;
	}
	if(i == M)
		cout << 0;
	else
		cout << i+1;
	
	return 0;
}

문제가 dp의 냄새를 강하게 풍기고 있는데, 단순 dp를 적용은 불가능하고 두 가지를 해결해야 한다.

첫 번째로는

n번째 까지의 최선의 선택이 n+1번째 집을 칠할 때의 최선의 선택이 아닐수도 있다는 것이다.

n에서 red를 골랐는데, n+1번째의 색칠 비용이 blue, green이 1000이고, red가 1이라면,

n에서 red를 고르는 선택이 잘못된 선택으로 변할수도 있다는 것이다.

이 문제를 해결하는 법은 간단하다.

n에서 red를 골랐을 경우, green을 골랐을 경우, 그리고 blue를 골랐을 경우 최선의 선택을 각각 보관하는 것이다.

그렇다면 n+1일때 n의 색깔별 최선과 n+1번째의 색깔 별 비용을 고려하여 최선의 선택이 가능해진다.

vector<vector<int>> dp(N, vector<int>(3));
dp[0] = cost[0];

for(int n = 1; n<N; n++) { // dp n번째 집이고, 0번에 i를 칠했으며, n번째에 j를 골랐을 때의 최적값
    for (int i = 0; i < 3; i++) {
        dp[n][i] = cost[n];
        dp[n][i] += (dp[n-1][(i+1)%3] < dp[n-1][(i+2)%3] ? dp[n-1][(i+1)%3] : dp[n-1][(i+2)%3]);
    }
}

그러나 하나의 문제가 더 존재한다.

바로 1번과 N번 집의 색상이 달라야 한다는 점

이를 고려하는 방법은 첫 번째 문제의 해결방법과 유사하게, 첫 번째 집의 색상별로 최선의 선택을 보관하였다가,

첫 번째 집과 다른 색상의 최선의 선택 두 가지, 총 여섯가지에 대해 최선을 비교하면 되는 것이다.

첫 번째 집의 색상별로 최선의 선택을 보관하는 방법은, 말 그대로 첫 번째 집의 색상 별로 또 별도의 배열을 만들어

동적 계산을 진행하는 것이다.

vector<vector<vector<int>>> dp(N, vector<vector<int>>(3, vector<int>(3)));
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        dp[1][i][j] = cost[0][i];
        if(i == j) {
            dp[1][i][j] += 1001;
        }
        else
            dp[1][i][j] += cost[1][j];
    }
}
for(int n = 2; n<N; n++) { // dp n번째 집이고, 0번에 i를 칠했으며, n번째에 j를 골랐을 때의 최적값
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            dp[n][i][j] = cost[n][j];
            dp[n][i][j] += (dp[n-1][i][(j+1)%3] < dp[n-1][i][(j+2)%3] ? dp[n-1][i][(j+1)%3] : dp[n-1][i][(j+2)%3]);
        }

    }
}

int best = -1;
for(int i = 0 ; i < 3 ; i ++) {
    for (int j = 0; j < 3; j++) {
        if(i==j) continue;
        if(best == -1 || best > dp[N-1][i][j])
            best = dp[N-1][i][j];
    }
}
cout << best;

이번에는 확실히 논리적으로 가능과 불가능의 여부를 확인하여 진행했다.

문제가 비교적 간단해서 가능했지만, 이렇게 하는 습관을 들여야

좀더 어려운 문제도 비약으로 인한 오류를 방지할 수 있을 거라 희망한다.

너무 쉬운 문제인데 너무 어렵게 생각해서 며칠의 시간이 갈린지 모르겠다.

문자열 A, B로 생각했을 때,

B를 하나씩 순차적으로 탐색하면서 A의 인덱스 별로 최장 길이를 담은 DP 배열을 만들어

A 내 해당 인덱스의 문자와 B의 현재 탐색중인 문자가 같으면 최장 길이+1을 해서 갱신 해 준다.

vector<vector<int>> dp(1, vector<int>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
    auto b = B[b_i];

    int longest = 0;
    int long_idx = -1;
    vector<int> cur_dp(A.size());
    for (int a_i = 0; a_i < A.length(); a_i++) {
        auto a = A[a_i];
        if (b == a) {
            cur_dp[a_i] = longest + 1;
        }
        else {
            cur_dp[a_i] = dp[b_i][a_i];
        }
        if (dp[b_i][a_i] > longest) {
            longest = dp[b_i][a_i];
        }
    }
    dp.push_back(cur_dp);
}

이렇게 하면 dp의 마지막 인덱스 (b 탐색이 모두 끝난 후의 상태)에서 최장 값을 찾으면 그 값이 정답이 된다.

사실 dp[B.length][A.length] 사이즈의 배열은 필요 없는데, 바로 이전 값만 참고하기 때문에,

1차원의 크기는 2로만 두어도 되며, 혹은 추가적으로 검토를 해서 1차원으로 만들 수도 있을 텐데,

공간복잡도를 고민해야 할 문제는 아니기 때문에 넘어가도 된다고 우선 판단했다.

이렇게 최장값을 찾는 것은 쉽지만, 이 문자열을 복원하는 과정이 내게는 의외로 너무 큰 걸림돌이였다.

너무 간단해 보이는데 집중을 잘 못해서인지 수많은 시간을 낭비했다..

우선적으로 적용해 볼 수 있는 방법은 dp[b_i][a_i]에 값을 갱신해 줄 때 최장 값의 위치를 기록하는 방법이다.

vector<vector<int>> dp(1, vector<int>(A.size()));
vector<vector<int>> dp_idx(1, vector<int>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
    auto b = B[b_i];

    int longest = 0;
    int long_idx = -1;
    vector<int> cur_dp(A.size());
    vector<int> cur_dpidx(A.size());
    
    for (int a_i = 0; a_i < A.length(); a_i++) {
        auto a = A[a_i];
        if (b == a) {
            cur_dp[a_i] = longest + 1;
            cur_dpidx[a_i] = long_idx;
        }
        else {
            cur_dp[a_i] = dp[b_i][a_i];
            cur_dpidx[a_i] = dp_idx[b_i][a_i];
        }
        if (dp[b_i][a_i] > longest) {
            longest = dp[b_i][a_i];
            long_idx = a_i;
        }
    }
    dp.push_back(cur_dp);
    dp_idx.push_back(cur_dpidx);

}

이렇게 기록을 하면, 최장값을 찾은 후 해당 인덱스에서 순차적으로 돌아가면 문제가 생긴다.

어떤 문제냐면 b_idx를 탐색하는 과정에서, 최장값도 만들어지지만, 후반부의 B 문자를 A에서 검색하는 과정에서

이전 dp와 dp_idx 값이 갱신되는 문제가 생긴다. 이는 dp의 의도한 결과지만, 결과를 역추적하는 경우엔 문제가 발생한다.

따라서, 적절한 long_idx 외에도 b_idx가 주어져있어야 정상적으로 추적이 가능하다.

완성된 코드는 다음과 같다

struct IDX {
	int b_idx = -1;
	int a_idx = -1;
};

vector<vector<int>> dp(1, vector<int>(A.size()));
vector<vector<IDX>> dp_idx(1, vector<IDX>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
    auto b = B[b_i];

    int longest = 0;
    int long_idx = -1;
    vector<int> cur_dp(A.size());
    vector<IDX> cur_dpidx(A.size());
    for (int a_i = 0; a_i < A.length(); a_i++) {
        auto a = A[a_i];
        if (b == a) {
            cur_dp[a_i] = longest + 1;
            cur_dpidx[a_i] = { b_i, long_idx };
        }
        else {
            cur_dp[a_i] = dp[b_i][a_i];
            cur_dpidx[a_i] = dp_idx[b_i][a_i];
        }
        if (dp[b_i][a_i] > longest) {
            longest = dp[b_i][a_i];
            long_idx = a_i;
        }
    }
    dp.push_back(cur_dp);
    dp_idx.push_back(cur_dpidx);

}

int longest = 0;
int long_idx = -1;
for (int i = 0; i < A.length(); i++) {
    if (longest < dp[B.length()][i]) {
        longest = dp[B.length()][i];
        long_idx = i;
    }
}

cout << longest;
if (longest > 0) {
    cout << '\n';
    IDX cur_idx = { B.length(), long_idx };
    stack<char> result;
    while (true) {
        cur_idx = dp_idx[cur_idx.b_idx][cur_idx.a_idx];
        result.push(B[cur_idx.b_idx]);
        if (cur_idx.a_idx == -1) break;
    }
    while (!result.empty()) {
        cout << result.top();
        result.pop();
    }
}

역으로 추적은 하지만, 출력은 정방향으로 해야하기 때문에, stack을 사용해서 구현했다.

stringbuilder등을 쓰거나 간단한 메소드를 통해 reverse 하는 방법도 있을 것이다.

사실 알고리즘 문제풀이를 할 때 노래를 듣거나 유튜브를 틀어놓고 문제를 푸는데

이 때문에 집중력의 한계가 생겨 신중하게 생각해야 되는 부분을 비약해서 넘기거나 해결을 못하게 된다

이 부분을 꼭 주의해야겠다.

우연찮게도 바로 직전에 풀었던 문제의 아주 조금 변형된 문제가 나왔다

설마설마 하면서 작성했지만 이전 문제와 풀이방법이 아예 같다.

문제의 다른 점이라면, 원래는 두 학생간의 관계만 주어졌었는데, 이제는 일련의 순서를 보장해야 한다는 점이다.

그렇다면 이 부분만 기존에 맞게 적절히 변형해주면 기존 코드를 그대로 재사용할 수 있다.

vector<int> phase(N, 0);
vector<list<int>> singer_list(N, list<int>());

for (int i = 0; i < M; i++) {
    int n;
    cin >> n;
    vector<int> sub_pd_order(n);
    for(auto &item : sub_pd_order)
        cin >> item;

    for(int j = 0 ; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            singer_list[sub_pd_order[j] - 1].push_back(sub_pd_order[k] - 1);
            phase[sub_pd_order[k] - 1] += 1;
        }
    }
}

이 부분이 기존 코드를 그대로 차용하기 위해 만든 입력부 코드인데, 간단해서 바로 보면 이해되겠지만,

단순히 입력받은 순서를 그대로 순회하며 순서를 보장하는 두 인자간의 관계를 이전 코드의 입력 부에 매칭시켰다.

queue<int> order;
for (int idx = 0; idx < N; idx++) {
    if (phase[idx] == 0) {
        order.push(idx);
    }
}

vector<int> result;

while (!order.empty()) {
    auto cur = order.front();
    result.push_back(cur);
    order.pop();
    for (const auto& singer : singer_list[cur]) {
        phase[singer] -= 1;
        if (phase[singer] == 0)
            order.push(singer);
    }
}

if(result.size() == N) {
    for (auto& item : result)
        cout << item+1 << '\n';
}
else
    cout << 0;

핵심 코드는 언급한대로 아예 동일하다. 대신, 기존과는 다르게 불가능할 수도 있다는 전제가 붙기 때문에,

순서를 뽑는 대로 출력하는 것이 아닌, 벡터에 선 보관 후 가수의 수와 일치하지 않으면,

" 모든 가수를 희망하는 순서대로 정렬할 수 없다면 " 0을 출력하고 아니면 그대로 벡터를 출력해주도록 작성했다.

queue<int> order;
vector<int> phase(N, 0);
vector<list<int>> tall_list(N, list<int>());
for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    tall_list[a-1].push_back(b-1);
    phase[b-1]+=1;
}
for (int idx = 0 ; idx<N;idx++) {
    if (phase[idx] == 0) {
        order.push(idx);
    }
}

while (!order.empty()) {
    auto cur = order.front();
    cout << cur+1 << ' ';
    order.pop();
    for (const auto& tall : tall_list[cur]) {
        phase[tall] -= 1;
        if(phase[tall] == 0)
            order.push(tall);
    }
}

위상 정렬이 생각나는 문제였다.

아무래도 DP나 구현 문제들은 책정된 난이도가 다른 유형 대비 훨씬 어려운 느낌이 있다.

단순 위상 정렬을 생각하고 구현하면 됐고, 유의할 점은 공간복잡도를 초과하지 않아야 된다는 점이였는데

이는 본인보다 키 큰 인원의 정보를 담은 컨테이너를 동적 할당 해 주는 컨테이너로 지정하여 해결했다.

나보다 키 작은 사람들의 수를 담은 배열을 만들고, 나보다 키가 작은 사람이 없는 사람들을 우선적으로 배치한 후에

순차적으로 해당 배열에서 그 사람들보다 큰 사람에 값을 1씩 빼주다가 0이 되면 순서대로 줄을 세워서 해결했다.

말로 하면 복잡하지만 코드로 보면 매우 간단하다.

골드4 문제가 너무 어려운 것도 아니고 엄청 쉬운데 해결이 안되서 이틀동안 집중도 못하고 손을 못대고 있었는데,

다른 문제로 넘어가니 골드4 골드3을 쉽게 풀어서 좀 허탈했다. 아니면 우연찮게 접근법이 적절했었던 걸 수도 있다.

단순히 bruteforce로 할 수 있는 문제는 아니라고 생각했으며, 동적 계획법을 일부 활용해야 된다고 생각했다.

그렇게 판단했다면 먼저 나는 이렇게 정의하는 편이다

1. 배열의 구성을 어떻게 설정할 것이며, 인덱스가 의미하는 값은 무엇인지

2. 그럼 이 배열로 이전 값을 어떻게 활용해서 다음 값을 갱신할 것인지

미리 다 계산을 해놓고, 질문에 맞는 대답만 해줘도 된다고 생각했다.

코드를 점진적으로 발전시킨다는 가정으로, 최소한의 메모이제이션을 활용한 방법을 생각했고, 그렇다면

1. dp[start][end]으로, 해당 위치가 의미하는 정보는 start에서 end까지의 수열이 팰린드롬 수열인지를 가리킨다

2. 우선 팰린드롬인질 알기 위해선 실제로 전부 비교해보는 수 밖엔 없을텐데, 대신 start 부터 end까지가 팰린드롬이라면, start+1, end-1 ... 해서 start+i == start-end까지의 수열은 모두 팰린드롬일 수 밖에 없을 것이고, 이를 활용하기로 했다.

vector<vector<int>> dp(arr.size(), vector<int>(arr.size(), -1));

for (int length = arr.size() - 1; length >= 0; length--) {
    for (int start = 0; start + length < arr.size(); start++) {
        bool isP = true;
        int end = start + length;
        if (dp[start][end] != -1) continue;
        for (int i = 0; i < (length+1) / 2; i++) {
            if (arr[start + i] != arr[end - i]) {
                isP = false;
                break;
            }
        }
        dp[start][end] = isP;
        if (isP) {
            for (int i = 1; i < (length+1) / 2; i++) {
                dp[start + i][end - i] = isP;
            }
        }
    }
}

구현할 때 중요한 부분은, 긴 길이부터 먼저 학습을 해야 2번 방식을 최대한 활용할 수 있으므로, 최대 길이부터 시작한다는 점이였다.

그 외에는 참 일때만 2번에 해당하는 메모이제이션을 활용 (사실 맞는 표현인지 정확하진 않다)

그리고 이미 조사한 경우에는 팰린드롬 조사하는 반복문을 생략하기로 했다.

테스트하기 전에, 시간 초과를 우려하여, N을 미리 최대값을 주고 진행해도 문제없이 시간 내에 계산을 완료한다는 사실을 확인하고 제출했다.

문제를 풀때 너무 순수 직관에 의존해서 문제를 푸는 버릇이 있다. 코딩테스트를 통과하려면 이 직감을 기르는게 중요하겠고, 그 코딩테스트에서 요구하는 직감의 난이도가 높지는 않겠지만, 그럼에도 불구하고 문제들을 풀 때는 논리적으로 최대한 접근하는 자세를 가져야 될 것 같다.

해커톤 진행중에 오랜만에 시간을 내서 문제를 잠깐 풀었다.

문제가 워낙 기초적인 알고리즘에서 살짝의 변주가 있던 만큼 방법은 순간적으로 떠올랐는데, 문제가 있었다.

생각한 해결방법:

 1. 그래프를 임의의 두 서브그래프로 나누어 MST를 구하면 된다 -> 시간복잡도로 인해 실행 불가능

 2. (예측) MST를 먼저 만들고, MST에서 가장 가중치가 높은 간선을 제거하여 그래프를 나눈다.

1번이 문제가 의도하는 바이지만, 그대로 실행하는건 불가능한데, 이를 약간 변형하면 2번과 같은 방법이 될 것이다

대신, 2번의 최적해가 1번의 최적해와 일치한다는 증명이 가능해야 하는데, 가장 중요한 부분이지만, 막연한 직관으로 될거라 믿고 풀고 챗봇에게 추후 질의했다. 

딥시크의 추론에게 의존했는데, 사실 스스로 할줄 알아야 하는 것이라 풀어도 푼게 아니긴 하다..

재밌는 점이라면 오늘부턴가 ChatGPT에도 유사한 기능이 생겼다는 점. 걱정이 되긴 했나보다.

그렇다면 결론은 MST을 만들기만 하면 이 문제의 답은 따라온다는 것인데, 문제는 내가 UnionFind의 구현을 잊었다는 점이다. 사실 예전에는 굉장히 비효율적인 방식으로 구현했던 것 같은데 하는김에 제대로 해보고 싶어서 구현했다.

class UnionFind {
private:
    vector<int> parent; // 멤버 변수: 각 원소의 부모를 저장
    vector<int> rank;   // 멤버 변수: 각 트리의 랭크를 저장

public:
    // 생성자: size만큼의 원소를 초기화
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 1); // 초기 랭크는 1
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 초기화: 각 원소는 자기 자신을 가리킴
        }
    }

    // Find 연산: 경로 압축 적용
    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    // Union 연산: 랭크 기반 합치기
    bool Union(int a, int b) {
        int root_a = Find(a);
        int root_b = Find(b);
        if (root_a == root_b) return false; // 이미 같은 집합

        // 랭크 기반 합치기
        if (rank[root_a] > rank[root_b]) {
            parent[root_b] = root_a;
        }
        else if (rank[root_a] < rank[root_b]) {
            parent[root_a] = root_b;
        }
        else {
            parent[root_b] = root_a;
            rank[root_a] += 1;
        }
        return true;
    }
};

C++에서 오랜만에 Class를 구현하려다 좀 골머리를 앓았지만, 덕분에 그래프의 탐색에서 자주 쓰이는 유니온파인드를 한번 구현해볼 기회가 되서 좋았다.

또 간단한 거지만, 입력받은 간선을 비용순으로 오름차순 정렬해야 하는데, 구조체를 정렬할 때 키를 설정하는 방법이다

struct cost_set {
	int start, end, cost;
	bool operator< (const cost_set& s) {
		return cost < s.cost;
	}
};

~ main ~
	vector<cost_set> cost_vector(M);
	for (auto& cs : cost_vector)
		cin >> cs.start >> cs.end >> cs.cost;

	sort(cost_vector.begin(), cost_vector.end());

UnionFind를 구현하고 나면 이 문제를 푸는 것은 어이없게 간단하다. 그냥 MST의 cost에서 마지막 MST 간선을 빼주면 되는 것

	for (auto& cs : cost_vector) {
		if (union_find.Union(cs.start - 1, cs.end - 1)) {
			cost += cs.cost;
			max_mst_edge = cs.cost;
		}
	}
	cost -= max_mst_edge;

정말 쉬운 문제지만, 내 약점을 확인할 수 있는 기회였고, 이를 보완 해야겠다는 생각이 들었다.