[알고리즘] Greedy Method

// 통합 그래프 알고리즘 구현 파일
// 포함 알고리즘: DFS, TopoSort, SCC(Kosaraju), Kruskal, Prim, WidestPath, EFTF 구간 스케줄링, Box Stacking
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <fstream>
#include <algorithm>
#include <tuple>

using namespace std;

// ========================== 공통 변수 ==========================
int V, E;
vector<vector<pair<int, int>>> adj; // 가중치 포함 그래프
vector<vector<int>> graph, rev_graph;
vector<bool> visited;
vector<int> parent;

// ========================== DFS ==========================
void dfs_util(int u) {
    visited[u] = true;
    cout << u << " ";
    for (auto [v, _] : adj[u]) if (!visited[v]) dfs_util(v);
}
void DFS() {
    visited.assign(V, false);
    cout << "DFS 순회: "; dfs_util(0); cout << endl;
}

// ========================== Topological Sort (DAG 전용) ==========================
vector<int> topo_result;
void topo_dfs(int u) {
    visited[u] = true;
    for (auto [v, _] : adj[u]) if (!visited[v]) topo_dfs(v);
    topo_result.push_back(u);
}
void TopologicalSort() {
    visited.assign(V, false); topo_result.clear();
    for (int i = 0; i < V; i++) if (!visited[i]) topo_dfs(i);
    reverse(topo_result.begin(), topo_result.end());
    cout << "Topological Sort 결과: ";
    for (int x : topo_result) cout << x << " ";
    cout << endl;
}

// ========================== SCC (Kosaraju) ==========================
stack<int> finish_order;
vector<vector<int>> SCCs;
void dfs1(int u) {
    visited[u] = true;
    for (int v : graph[u]) if (!visited[v]) dfs1(v);
    finish_order.push(u);
}
void dfs2(int u, vector<int>& comp) {
    visited[u] = true; comp.push_back(u);
    for (int v : rev_graph[u]) if (!visited[v]) dfs2(v, comp);
}
void SCC_Kosaraju() {
    visited.assign(V, false);
    for (int i = 0; i < V; ++i) if (!visited[i]) dfs1(i);
    visited.assign(V, false);
    while (!finish_order.empty()) {
        int u = finish_order.top(); finish_order.pop();
        if (!visited[u]) {
            vector<int> comp; dfs2(u, comp);
            SCCs.push_back(comp);
        }
    }
    cout << "총 SCC 개수: " << SCCs.size() << endl;
    for (size_t i = 0; i < SCCs.size(); ++i) {
        cout << "SCC " << i + 1 << ": ";
        for (int v : SCCs[i]) cout << v << " "; cout << endl;
    }
}

// ========================== Kruskal MST ==========================
struct Edge { int u, v, w; };
vector<Edge> edges;
int find(int u) { return parent[u] == u ? u : parent[u] = find(parent[u]); }
bool unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    parent[v] = u; return true;
}
void Kruskal() {
    parent.resize(V); for (int i = 0; i < V; ++i) parent[i] = i;
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.w < b.w; });
    int mst_cost = 0;
    cout << "Kruskal MST 간선: \n";
    for (Edge e : edges) {
        if (unite(e.u, e.v)) {
            cout << e.u << " - " << e.v << " : " << e.w << endl;
            mst_cost += e.w;
        }
    }
    cout << "MST 총 비용: " << mst_cost << endl;
}

// ========================== Prim MST ==========================
void Prim() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<int> dist(V, 1e9); dist[0] = 0;
    vector<bool> inMST(V, false);
    pq.push({0, 0}); int mst_cost = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true; mst_cost += d;
        for (auto [v, w] : adj[u]) if (!inMST[v] && w < dist[v]) {
            dist[v] = w; pq.push({w, v});
        }
    }
    cout << "Prim MST 총 비용: " << mst_cost << endl;
}

// ========================== Widest Path ==========================
void WidestPath(int src) {
    vector<int> width(V, 0); width[src] = 1e9;
    priority_queue<pair<int, int>> pq; pq.push({1e9, src});
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        for (auto [v, cost] : adj[u]) {
            int min_width = min(w, cost);
            if (min_width > width[v]) {
                width[v] = min_width;
                pq.push({width[v], v});
            }
        }
    }
    cout << "Widest path 값: \n";
    for (int i = 0; i < V; ++i)
        cout << "0 → " << i << ": " << width[i] << endl;
}

// ========================== Earliest Finish Time First ==========================
struct Interval { int id, start, end; };
bool compatible(const Interval& a, const Interval& b) { return a.end <= b.start; }
void IntervalScheduling_EFTF(const string& fname) {
    ifstream in(fname);
    int n; in >> n;
    vector<Interval> jobs(n);
    for (int i = 0; i < n; ++i) in >> jobs[i].start >> jobs[i].end, jobs[i].id = i;
    sort(jobs.begin(), jobs.end(), [](Interval a, Interval b) { return a.end < b.end; });
    vector<int> selected;
    int last_end = -1;
    for (auto j : jobs) if (j.start >= last_end) {
        selected.push_back(j.id); last_end = j.end;
    }
    cout << "EFTF 선택된 작업 ID: "; for (int id : selected) cout << id << " "; cout << endl;
}

// ========================== 입력 및 실행 ==========================
void loadGraph(const string& fname) {
    ifstream in(fname);
    if (!in) { cerr << "파일 열기 실패!\n"; exit(1); }
    in >> V >> E;
    adj.assign(V, {});
    graph.assign(V, {}); rev_graph.assign(V, {}); edges.clear();
    for (int i = 0; i < E; ++i) {
        int u, v, w; in >> u >> v >> w;
        adj[u].push_back({v, w});
        graph[u].push_back(v);
        rev_graph[v].push_back(u);
        edges.push_back({u, v, w});
    }
    in.close();
}

int main() {
    cout << "그래프 입력 파일명 (예: input.txt): ";
    string fname; cin >> fname;
    loadGraph(fname);

    cout << "\n1: DFS\n2: Topological Sort\n3: SCC (Kosaraju)\n4: Kruskal MST\n5: Prim MST\n6: Widest Path (0기준)\n7: Interval Scheduling (EFTF)\n선택: ";
    int op; cin >> op;
    if (op == 1) DFS();
    else if (op == 2) TopologicalSort();
    else if (op == 3) SCC_Kosaraju();
    else if (op == 4) Kruskal();
    else if (op == 5) Prim();
    else if (op == 6) WidestPath(0);
    else if (op == 7) IntervalScheduling_EFTF("intervals.txt");
    else cout << "잘못된 입력\n";
    return 0;
}

/*
📘 사용법:
input.txt: 정점 수, 간선 수, u v w
intervals.txt: N, 각 작업의 시작/종료 시간
예시:
intervals.txt
5
1 4
2 5
3 6
5 7
6 9

컴파일: g++ -o graph graph.cpp
실행: ./graph
*/