[Programmers] 스마트한 프로도 - [그래프 이론, 그리디]

[Programmers] 스마트한 프로도 - [그래프 이론, 그리디]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/1840

문제 요약

초기 매칭 $M_0$와 목표 매칭 $M_t$가 주어질 때, 한 번에 하나의 간선을 추가하거나 삭제하여 $M_0$를 $M_t$로 변환해야 한다. 단, 변환 과정에서 생성되는 모든 중간 단계의 매칭 $M_i$는 크기가 $k-2$ 이상이어야 한다. 이 조건을 만족하는 변환 과정(간선 삭제/추가 순서)을 반환한다.

접근 방법

• 자료구조: 인접 리스트(Adjacency List), 해시 셋(Set)
• 알고리즘: 그리디(Greedy), 깊이 우선 탐색(DFS)
• 핵심 아이디어:
  1. 대칭 차집합($M_0 \oplus M_t$): 공통 간선은 무시하고, 서로 다른 간선들로만 그래프를 구성하면 경로(Path) 또는 사이클(Cycle) 형태의 컴포넌트들로 분리된다.
  2. 우선순위 부여: 매칭 크기 제약($\ge k-2$)을 지키기 위해, 매칭 크기를 증가시키는 컴포넌트를 먼저 처리하고, 감소시키는 컴포넌트를 나중에 처리한다.
     • 1순위: $M_t$-Heavy (증가)
     • 2순위: Even Path (유지)
     • 3순위: $M_0$-Heavy (감소)
     • 4순위: Cycle (감소 후 유지)
  3. 방향성 정렬: 짝수 길이나 사이클의 경우, 간선 삭제와 추가가 서로 의존적이므로 올바른 순서(제거 후 추가)가 가능하도록 경로의 방향을 조정(Reverse/Rotate)해야 한다.

풀이 코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <tuple>
#include <map>

using namespace std;

// 간선 정보를 담을 구조체
struct Edge {
    int id;
    int type; // 0: M0, 1: Mt
};

// 컴포넌트 정보
struct Component {
    int priority; // 1: Mt-heavy, 2: Even, 3: M0-heavy, 4: Cycle
    vector<Edge> path; 
};

// 우선순위 정렬 함수
bool compareComponents(const Component& a, const Component& b) {
    return a.priority < b.priority;
}

vector<vector<int>> solution(int n, int m, vector<int> a, vector<int> b, int k, int m1, int m2, vector<int> e1, vector<int> e2) {
    vector<vector<int>> answer;

    set<int> set_e1(e1.begin(), e1.end()); // M0
    set<int> set_e2(e2.begin(), e2.end()); // Mt

    // 인접 리스트 구성 (대칭 차집합만)
    vector<vector<pair<int, int>>> adj(n + 1);
    vector<int> degree(n + 1, 0);
    map<int, int> edge_type_map; // ID -> Type

    for (int i = 0; i < m; ++i) {
        int id = i + 1;
        bool in_m0 = set_e1.count(id);
        bool in_mt = set_e2.count(id);

        if (in_m0 != in_mt) { // 대칭 차집합
            int type = in_mt ? 1 : 0;
            adj[a[i]].push_back({b[i], id});
            adj[b[i]].push_back({a[i], id});
            degree[a[i]]++;
            degree[b[i]]++;
            edge_type_map[id] = type;
        }
    }

    vector<bool> visited_edge(m + 1, false);
    vector<bool> visited_node(n + 1, false);
    vector<Component> components;

    for (int i = 1; i <= n; ++i) {
        if (degree[i] > 0 && !visited_node[i]) {
            // 1. 연결 요소(컴포넌트) 노드 수집
            vector<int> nodes;
            vector<int> q = {i};
            visited_node[i] = true;
            nodes.push_back(i);

            int head = 0;
            while(head < q.size()){
                int curr = q[head++];
                for(auto& p : adj[curr]){
                    int nxt = p.first;
                    if(!visited_node[nxt]){
                        visited_node[nxt] = true;
                        nodes.push_back(nxt);
                        q.push_back(nxt);
                    }
                }
            }

            // 2. 경로의 시작점 찾기 (차수 1인 노드)
            int start_node = nodes[0];
            bool is_cycle = true;
            for(int u : nodes){
                if(degree[u] == 1) {
                    start_node = u;
                    is_cycle = false;
                    break;
                }
            }

            // 3. 경로 구성 (DFS/Traversal)
            vector<Edge> path;

            // 경로 추적을 위한 재설정 (visited_edge 사용)
            // 현재 컴포넌트 내에서만 탐색
            int path_curr = start_node;
            while(true){
                bool moved = false;
                for(auto& p : adj[path_curr]){
                    int nxt = p.first;
                    int eid = p.second;
                    if(!visited_edge[eid]){
                        visited_edge[eid] = true;
                        path.push_back({eid, edge_type_map[eid]});
                        path_curr = nxt;
                        moved = true;
                        break; 
                    }
                }
                if(!moved) break;
            }

            // 4. 컴포넌트 분류 및 정규화
            Component comp;
            comp.path = path;

            if (is_cycle) {
                comp.priority = 4;
                // 사이클은 M0가 맨 앞에 오도록 회전 (삭제 우선 전략)
                // [Mt, M0, Mt, M0...] -> [M0, Mt, M0, Mt...]
                int m0_idx = -1;
                for(int k=0; k<comp.path.size(); k++){
                    if(comp.path[k].type == 0) { m0_idx = k; break; }
                }
                if(m0_idx != -1 && m0_idx != 0){
                     vector<Edge> new_path;
                     for(int k=m0_idx; k<comp.path.size(); k++) new_path.push_back(comp.path[k]);
                     for(int k=0; k<m0_idx; k++) new_path.push_back(comp.path[k]);
                     comp.path = new_path;
                }
            } else {
                int first = comp.path.front().type;
                int last = comp.path.back().type;

                if (first == 1 && last == 1) { 
                    comp.priority = 1; // Mt ... Mt (Mt-Heavy)
                } else if (first == 0 && last == 0) {
                    comp.priority = 3; // M0 ... M0 (M0-Heavy)
                } else {
                    comp.priority = 2; // Even Path
                    // Even Path는 반드시 Mt로 시작해서 M0로 끝나야 함 (Mt ... M0)
                    // 그래야 앞에서부터 (Rem M0, Add Mt)가 가능함
                    if (first == 0) {
                        reverse(comp.path.begin(), comp.path.end());
                    }
                }
            }
            components.push_back(comp);
        }
    }

    // 5. 우선순위대로 처리
    sort(components.begin(), components.end(), compareComponents);

    for (const auto& c : components) {
        vector<Edge> p = c.path;

        if (c.priority == 1) { // Mt-Heavy: [Mt, M0, Mt, M0, ..., Mt]
            if (p.size() == 1) {
                answer.push_back({1, p[0].id});
            } else {
                for (size_t k = 1; k < p.size(); k += 2) {
                    answer.push_back({0, p[k].id});   // Remove M0
                    answer.push_back({1, p[k-1].id}); // Add Mt (Left of M0)
                }
                answer.push_back({1, p.back().id}); // Add Last Mt
            }
        } 
        else if (c.priority == 2) { // Even: [Mt, M0, Mt, M0 ...] (정규화됨)
            for (size_t k = 1; k < p.size(); k += 2) {
                answer.push_back({0, p[k].id});   // Remove M0
                answer.push_back({1, p[k-1].id}); // Add Mt
            }
        }
        else if (c.priority == 3) { // M0-Heavy: [M0, Mt, M0 ...]
            answer.push_back({0, p[0].id}); // Remove First M0
            for (size_t k = 2; k < p.size(); k += 2) {
                answer.push_back({0, p[k].id});   // Remove Next M0
                answer.push_back({1, p[k-1].id}); // Add Next Mt
            }
        }
        else if (c.priority == 4) { // Cycle: [M0, Mt, M0, Mt ...] (정규화됨)
            answer.push_back({0, p[0].id});
            for (size_t k = 2; k < p.size(); k += 2) {
                answer.push_back({0, p[k].id}); 
                answer.push_back({1, p[k-1].id});
            }
            answer.push_back({1, p.back().id});
        }
    }

    return answer;
}

시간/공간 복잡도

• 시간 복잡도: $O(N + M)$
• 공간 복잡도: $O(N + M)$

실행 결과

• 메모리: (채점 결과에 따라 기입)
• 시간: (채점 결과에 따라 기입)

핵심 포인트

1. 대칭 차집합 그래프 분해: 문제를 독립적인 컴포넌트(경로/사이클) 문제로 분할하여 생각합니다.
2. 그리디(Greedy) 우선순위: 매칭 크기를 늘려주는 작업($M_t$-Heavy)을 먼저 수행하여 '버퍼'를 확보해야 중간 과정에서 크기 제약 조건을 만족시킬 수 있습니다.
3. 순서 의존성 해결: Even Path와 Cycle의 경우, $M_0$를 먼저 제거하고 $M_t$를 추가해야 하는 의존성이 있습니다. 이를 위해 Path를 뒤집거나(Reverse) Cycle을 회전(Rotate)시켜 처리 순서를 올바르게 맞춰주어야 합니다.

예제 확인

• 예제 1: $M_0={3, 6}, M_t={2, 4}$ (Even Path)
  • 기존 방식(M0 시작)은 충돌 발생.
  • 개선 방식(Mt 시작 $2-3-4-6$) 적용 시: Remove 3 -> Add 2 -> Remove 6 -> Add 4 (성공).