1월27일 - 정리정돈[BOJ/12918]

문제 설명

철수는 방을 정리하려고 한다. 방을 정확히 절반으로 나누는 y축 선대칭으로 물건들이 정렬되도록 배치하고자 한다. 물건의 위치와 대칭 위치 간 이동 거리는 유클리드 거리로 계산되며, 물건들이 이동하는 거리의 합을 최소화해야 한다.

문제의 핵심은 다음과 같다:

• 물건들의 위치는 2차원 좌표로 주어진다.
• 각 물건은 반드시 대칭된 위치에 존재해야 하며, 이 위치에 도달하기 위해 이동 거리를 최소화해야 한다.

---

해결 방법

이 문제는 이분 매칭과 최소 비용 최대 유량(MCMF) 알고리즘을 활용하여 해결한다.

1. 이분 매칭 모델링

   • 주어진 물건들의 위치를 기준으로 대칭 위치를 생성한다.
   • 실제 물건들과 대칭된 물건들 간 매칭 문제로 변환한다.

2. 최소 비용 최대 유량

   • 각 물건을 소스와 연결하고, 대칭 위치를 싱크와 연결한다.
   • 물건과 대칭 위치 간의 비용은 해당 두 좌표 사이의 유클리드 거리이다.
   • 최소 비용으로 모든 물건을 대칭 위치에 매칭한다.

3. 거리 계산

   • 두 점 사이의 거리는 다음 공식을 사용한다:
     [
     D = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}
     ]

---

코드

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define loop(i, start, end) for (int i = (start); i < (end); i++)
using namespace std;
typedef pair<int, int> Point;

void setupFastIO() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

const int MAX_SIZE = 202;
int objectCount;
Point objects[100];

// Minimum Cost Maximum Flow 구조체
struct MinCostMaxFlow {
    struct Edge {
        int destination, capacity, reverseIndex;
        double cost;

        Edge(int dest, int cap, int rev, double cost)
            : destination(dest), capacity(cap), reverseIndex(rev), cost(cost) {}
    };

    vector<Edge> edges[MAX_SIZE];
    int source, sink;

    void initialize() {
        loop(i, 0, MAX_SIZE) edges[i].clear();
    }

    void addEdge(int from, int to, int cap, double cost) {
        edges[from].emplace_back(to, cap, edges[to].size(), cost);
        edges[to].emplace_back(from, 0, edges[from].size() - 1, -cost);
    }

    void setSourceSink(int src, int snk) {
        source = src;
        sink = snk;
    }

    double distances[MAX_SIZE];
    int parentNode[MAX_SIZE], parentEdge[MAX_SIZE];
    bool inQueue[MAX_SIZE];

    bool shortestPath() {
        fill(distances, distances + MAX_SIZE, 1e9);
        fill(inQueue, inQueue + MAX_SIZE, false);

        queue<int> q;
        q.push(source);
        distances[source] = 0;
        inQueue[source] = true;
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            inQueue[current] = false;
            for (int i = 0; i < edges[current].size(); i++) {
                int next = edges[current][i].destination;
                int cap = edges[current][i].capacity;
                double cost = edges[current][i].cost;
                if (cap > 0 && distances[next] > distances[current] + cost + 1e-9) {
                    distances[next] = distances[current] + cost;
                    parentNode[next] = current;
                    parentEdge[next] = i;
                    if (!inQueue[next]) {
                        q.push(next);
                        inQueue[next] = true;
                    }
                }
            }
        }
        return distances[sink] != 1e9;
    }

    double findMatching() {
        double result = 0;
        loop(i, 0, objectCount) {
            shortestPath();
            result += distances[sink];
            for (int j = sink; j != source; j = parentNode[j]) {
                int reverseIdx = parentEdge[j];
                edges[parentNode[j]][reverseIdx].capacity--;
                edges[j][edges[parentNode[j]][reverseIdx].reverseIndex].capacity++;
            }
        }
        return result;
    }
} FlowSolver;

// 두 점 사이의 거리 계산
double calculateDistance(Point a, Point b) {
    double dx = (double)a.first - b.first;
    double dy = (double)a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

void solve() {
    cin >> objectCount;
    loop(i, 0, objectCount) cin >> objects[i].first >> objects[i].second;

    FlowSolver.initialize();
    FlowSolver.setSourceSink(objectCount * 2, objectCount * 2 + 1);

    loop(i, 0, objectCount) {
        FlowSolver.addEdge(FlowSolver.source, i * 2, 1, 0);
        FlowSolver.addEdge(i * 2 + 1, FlowSolver.sink, 1, 0);
    }

    loop(i, 0, objectCount) {
        loop(j, 0, objectCount) {
            if (i == j) continue;
            FlowSolver.addEdge(i * 2, j * 2 + 1, 1, calculateDistance(objects[i], objects[j]));
        }
    }

    cout << fixed << setprecision(3) << FlowSolver.findMatching() << '\n';
}

int main() {
    setupFastIO();
    solve();
    return 0;
}

코드 설명

주요 로직

1. 입력 처리

   • 물건들의 좌표를 입력받아 저장한다.

2. MCMF 초기화

   • 모든 물건을 소스 노드와 연결하고, 매칭 위치를 싱크와 연결한다.
   • 각 물건과 매칭 위치 간의 비용은 거리로 설정한다.

3. 최소 비용 계산

   • shortestPath 함수로 최소 비용을 계산한다.
   • 플로우를 증가시키며 총 비용을 누적한다.

4. 거리 계산

   • 최종적으로 물건들을 정렬한 후 최소 비용을 출력한다.

So...

이 문제는 최소 비용 최대 유량과 이분 매칭 알고리즘의 조합을 학습할 수 있는 좋은 예제다. 물건들을 대칭으로 정렬하는 문제를 그래프 문제로 변환하는 과정에서 흥미로웠고, 특히 유클리드 거리 계산과 비용 최적화 부분에서 많은 고민을 했다. 이러한 접근법은 다른 최적화 문제에도 응용 가능하다.