[백준/BOJ C++] 11111번 : 두부장수 장홍준2 / 10937번 : 두부 모판 자르기 (MCMF)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11111번 : 두부장수 장홍준2, 10937번 : 두부 모판 자르기 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량(MCMF) 알고리즘에 대한 이해가 필요합니다.

 

 

11111번 : 두부장수 장홍준2

11111번: 두부장수 장홍준 2

 

두부를 위와 같이 (가로 세로 관계없이) 2×1의 크기로 잘라 1×1 크기 두부는 버리고 나머지 중에서 위의 가격표대로 가격을 합산한다고 할 때, 두부 가격의 합의 최댓값을 구하는 문제입니다.

 

 

 

두부를 체스판이라고 생각하고 2×1의 크기로 자를 경우 반드시 두 조각 중 한 조각은 검은 칸, 나머지 한 조각은 하얀 칸에 포함되므로 이를 이용하여 검은 칸에 들어가는 노드(예를 들면 (i+j)%2 == 0)와 흰 칸에 들어가는 노드(예를 들면 (i+j)%2 == 1)로 두 그룹을 나누어 이들이 인접한 칸일 경우에만 간선을 연결하는 방식으로 최대 유량 문제로 바꿔 생각할 수 있습니다.

 

따라서 위의 모식도와 같이 그래프를 연결지을 수 있고, 문제에서 N과 M의 범위는 최대 50이기 때문에 모든 칸의 수는 2500 이하입니다.

(위의 모식도에서 화살표 위의 파란 숫자는 Capacity, 빨간 숫자는 Cost에 해당합니다.)

이를 이용하여 Sour와 Sink, 그리고 각 배열 크기의 최대치를 잡아줄 수 있습니다.

 

그리고 이 문제에서는 1칸짜리 두부는 그냥 버리기 때문에, 선택되지 않은 칸은 언제든 0의 비용으로 Sink에 도달할 수 있어야 합니다.

따라서 왼쪽 그룹의 노드들은 모두 Sink로 연결지어줍니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 2505
#define INF 1000000000
using namespace std;

int N, M, Sour = 2501, Sink = 2502;
int Capacity[MAX][MAX] = {}, Flow[MAX][MAX] = {}, SinCost[MAX][MAX] = {};
vector<int> Line[MAX];

char Map[51][51];
int MapToCost[6][6] = {{10, 8, 7, 5, 0, 1}, {8, 6, 4, 3, 0, 1}, {7, 4, 3, 2, 0, 1}, {5, 3, 2, 2, 0, 1}, {0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 0, 0}};

void AddLine(int From, int To) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = 1;
    int Cost;
    if(From <= 2500 && To <= 2500) Cost = -MapToCost[Map[(From-1)/M+1][(From-1)%M+1]-'A'][Map[(To-1)/M+1][(To-1)%M+1]-'A'];
    else Cost = 0;
    SinCost[From][To] = Cost, SinCost[To][From] = -Cost;
}

int MCMF() {
    int CostSum = 0;
    while(true) {
        bool isInQueue[MAX] = {};
        int Parent[MAX] = {};
        int Cost[MAX];
        fill(Cost, Cost+MAX, INF);
        Cost[Sour] = 0;

        queue<int> Queue;
        Queue.push(Sour);
        isInQueue[Sour] = true;

        while(!Queue.empty()) {
            int Curr = Queue.front();
            Queue.pop();
            isInQueue[Curr] = false;
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0
                   && Cost[Curr] + SinCost[Curr][Next] < Cost[Next]) {
                    Cost[Next] = Cost[Curr] + SinCost[Curr][Next];
                    Parent[Next] = Curr;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        if(!Parent[Sink]) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Parent[i])
            Amount = min(Amount, Capacity[Parent[i]][i] - Flow[Parent[i]][i]);
        for(int i=Sink; i!=Sour; i=Parent[i]) {
            CostSum += Amount*SinCost[Parent[i]][i];
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
    }
    return CostSum;
}

int main() {
    scanf("%d %d\n", &N, &M);
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) Map[i][j] = getchar();
        getchar();
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            int Node = (i-1)*M+j;
            if((i+j)%2 == 0) {
                AddLine(Sour, Node);
                if(i > 1) AddLine(Node, Node-M);
                if(i < N) AddLine(Node, Node+M);
                if(j > 1) AddLine(Node, Node-1);
                if(j < M) AddLine(Node, Node+1);
            }
            AddLine(Node, Sink);
        }
    printf("%d", -MCMF());
}

 

코드는 일반적인 MCMF 알고리즘과 비슷하고, 단지 Map의 Char 값을 Int로 변경하는 과정에서 배열을 활용하였으며, E 등급의 두부가 없기 때문에 임의로 E 칸을 넣어 이들의 값을 0으로 정의했습니다. (어차피 입력이 주어지지 않아 사용될 일 없으므로 결과에 무관)

 

 

 

 

10937번 : 두부 모판 자르기

10937번: 두부 모판 자르기

 

KOI 2006 고등부 2번 문제로 출제되었던 KOI 기출 문제입니다.

위의 문제와 동일하고 입력부의 범위만 감소하였기 때문에, 위의 문제의 풀이 코드로 완전히 커버되는 문제입니다.

MapToCost 배열 부분만 int MapToCost[6][6] = {{100, 70, 40}, {70, 50, 30}, {40, 30, 20}};와 같이 수정해주면 정답 처리를 받을 수 있습니다.

 

 

 

 

 

---

+ 추가 내용

Edge Struct를 이용하여 구현한 코드를 추가합니다.

(14424번 : 두부장수 장홍준 3 풀이하려다가 시간 초과 발생함)

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 40005
#define INF 1000000000
using namespace std;

int N, M, Sour = 40001, Sink = 40002;
char Map[201][201];
int MapToCost[6][6] = {{10, 8, 7, 5, 0, 1}, {8, 6, 4, 3, 0, 1}, {7, 4, 3, 2, 0, 1}, {5, 3, 2, 2, 0, 1}, {0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 0, 0}};

struct Edge {
    int Next, Capacity, Cost, Flow;
    Edge* Rev;
    Edge(int Next_, int Capacity_, int Cost_) : Next(Next_), Capacity(Capacity_), Cost(Cost_), Flow(0) {}
    int Remain() { return Capacity - Flow; }
    void AddFlow(int Amount) {
        Flow += Amount;
        Rev->Flow -= Amount;
    }
};
vector<Edge*> Line[MAX];

void AddLine(int Curr, int Next) {
    int Cost;
    if(Curr <= 40000 && Next <= 40000) Cost = -MapToCost[Map[(Curr-1)/M+1][(Curr-1)%M+1]-'A'][Map[(Next-1)/M+1][(Next-1)%M+1]-'A'];
    else Cost = 0;
    Edge* E = new Edge(Next, 1, Cost);
    Edge* RevE = new Edge(Curr, 0, -Cost);
    E->Rev = RevE, RevE->Rev = E;
    Line[Curr].push_back(E), Line[Next].push_back(RevE);
}

int MCMF() {
    int CostSum = 0;
    while(true) {
        Edge* Path[MAX];
        int Prev[MAX]; fill(Prev, Prev+MAX, -1);
        int Cost[MAX]; fill(Cost, Cost+MAX, INF); Cost[Sour] = 0;
        queue<int> Queue; Queue.push(Sour);
        bool inQueue[MAX] = {}; inQueue[Sour] = true;

        while(!Queue.empty()) {
            int Curr = Queue.front(); Queue.pop();
            inQueue[Curr] = false;
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i]->Next;
                if(Line[Curr][i]->Remain() > 0 && Cost[Curr] + Line[Curr][i]->Cost < Cost[Next]) {
                    Cost[Next] = Cost[Curr] + Line[Curr][i]->Cost;
                    Prev[Next] = Curr;
                    Path[Next] = Line[Curr][i];
                    if(!inQueue[Next]) Queue.push(Next), inQueue[Next] = true;
                }
            }
        }
        if(Prev[Sink] == -1) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Prev[i])
            Amount = min(Amount, Path[i]->Remain());
        for(int i=Sink; i!=Sour; i=Prev[i]) {
            CostSum += Amount*Path[i]->Cost;
            Path[i]->AddFlow(Amount);
        }
    }
    return CostSum;
}

int main() {
    scanf("%d %d\n", &N, &M);
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) Map[i][j] = getchar();
        getchar();
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            int Node = (i-1)*M+j;
            if((i+j)%2 == 0) {
                AddLine(Sour, Node);
                if(i > 1) AddLine(Node, Node-M);
                if(i < N) AddLine(Node, Node+M);
                if(j > 1) AddLine(Node, Node-1);
                if(j < M) AddLine(Node, Node+1);
            }
            AddLine(Node, Sink);
        }
    printf("%d", -MCMF());
}