백준 11111 (C++) 두부장수 장홍준 2

최초 업로드: 2025-04-16 14:16:26

최근 수정 시간: 2025-07-25 09:48:54

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 두부장수 장홍준 2

#### [문제 링크](https://www.acmicpc.net/problem/11111)

## 문제 설명

장홍준은 참 특이한 두부장수이다. 세로크기 N, 가로크기 M인 두부판을 가지고 2x1짜리 두부로 잘라서 판다. 그런데, 두부판의 위치마다 등급이 다르다. 그리고 2x1짜리에 등급이 어떻게 매겨지느냐에 따라 두부의 값도 천차만별이 된다. 다음 등급표를 보자.

위의 표는 2x1짜리 두부의 등급에 따라 매겨지는 두부의 가격표다. 예를 들어 “AC" 두부의 가격은 7이고, ”DB" 두부의 가격은 3이다.

세로크기 N, 가로크기 M의 두부판이 주어진다. 각 칸마다 두부의 등급이 A, B, C, D, F로 매겨져 있다. 홍준이는 전체 두부가격의 합을 최대가 되게 두부를 자르려고 한다. 2x1짜리 두부로 잘라내고 남은 한 칸짜리 두부는 가격이 0이기 때문에 버린다. 홍준이를 도와 가격이 최대가 되게 두부판을 자르는 프로그램을 작성하시오.

위 그림은 N=4, M=4 인 두부판의 한 예이다. 오른쪽 그림이 잘라낸 두부가격의 합을 최대로 한 것이다. 한 칸짜리는 쓸모없으므로 버린다.

## 입력

첫째 줄에는 두부판의 세로크기 N, 가로크기 M이 주어진다. N, M은 1이상 50이하의 정수이다. 그 다음 N줄에 걸쳐 M개의 문자가 주어진다. 각 문자는 그 칸의 두부의 등급을 나타내며 A, B, C, D, F 중 하나로 주어진다.

## 출력

첫째 줄에 잘라낸 두부가격 합의 최댓값을 출력한다.

## 풀이
#### 체스판 색처럼 두가지 색으로 나눈 다음 MCMF 알고리즘을 써서 풀면 된다. MCMF로 최대 점수를 찾는 방법은 모든 cost를 -1 곱해서 최소 점수를 구한 후, 결과로 나온 값에 -1 곱해주면 된다. 여기서 주의할 점은, 최대 플로우가 최대 점수라는 보장은 없어서 체크를 해줘야한다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 2502;
const int S = MAX-2;
const int E = MAX-1;
const int score[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}, // E는 없음
 {1, 1, 1, 1, 0, 0},
};
char arr[50][50];
int f[MAX][MAX], cost[MAX][MAX], curCost[MAX], prv[MAX], inQueue[MAX];
vector<vector<int>> conn(MAX);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 cin >> arr[i][j];
 }
 }

for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 int cur = i*m+j;
 if(i%2==j%2) {
 conn[S].push_back(cur); // 순방향
 conn[cur].push_back(S); // 역방향
 f[S][cur]=-1;
 for(int k=0;k<4;k++) {
 int nx = i+dx[k];
 int ny = j+dy[k];
 if(nx<0 || nx>=n || ny<0 || ny>=m) continue;

int next = nx*m+ny;
                    conn[cur].push_back(next); // 순방향
                    conn[next].push_back(cur); // 역방향
                    f[cur][next]=-1;
                    cost[cur][next] = -score[arr[i][j]-'A'][arr[nx][ny]-'A']; // 순방향
                    cost[next][cur] = -cost[cur][next]; // 역방향
                }
            } else {
                conn[cur].push_back(E); // 순방향
                conn[E].push_back(cur); // 역방향
                f[cur][E]=-1;
            }
        }
    }

int totalCost=0;
 while(true) {
 queue<int> q; q.push(S);
 memset(prv, -1, sizeof prv);
 fill(curCost, curCost+MAX, INF);
 inQueue[S]=true;
 curCost[S]=0;
 while(!q.empty()) {
 int cur = q.front(); q.pop();
 inQueue[cur] = false;
 for(int next:conn[cur]) {
 if(-f[cur][next]>0 && curCost[next]>curCost[cur]+cost[cur][next]) {
 prv[next] = cur;
 curCost[next] = curCost[cur]+cost[cur][next];
 if(!inQueue[next]) {
 inQueue[next]=true;
 q.push(next);
 }
 }
 }
 }
 if(curCost[E]>0) break;

for(int i=E;i!=S;i=prv[i]) {
 f[prv[i]][i]++;
 f[i][prv[i]]--;
 }
 totalCost += curCost[E];
 }
 cout << -totalCost;
}
```