이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11405번 ~ 11407번 : '책 구매하기 1~3' 문제의 풀이 코드와 해설을 다루고 있습니다.
문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량 알고리즘(MCMF 알고리즘)에 대한 이해가 필요합니다.
11405번 : 책 구매하기
11405번: 책 구매하기
총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각
www.acmicpc.net
N명의 사람들이 각각 조건에 맞게 책을 구매하려고 하고 배송비가 소모된다고 할 때, 배송비의 최솟값을 구하는 문제입니다.
'비용'이라는 개념이 등장하고 이것의 최솟값을 구해야 하며, 무엇보다도 사람과 서점을 노드로 만들어 적절한 그래프를 만들 수 있으므로 최소 비용 최대 유량 알고리즘을 사용하면 쉽게 풀리는 문제임을 알 수 있습니다.
여기서는 간단하게 그림 설명으로 그래프를 구체적으로 어떻게 구현할지만 설명한 뒤 풀이 코드만 정리하고 넘어가도록 하겠습니다.
노드 번호를 매기는 것은 푸는 사람 마음이겠지만, 저의 경우에는 예시를 들자면 위와 같이 번호를 매겼습니다. (보라색)
간선에 표시된 빨간색 기호는 Capacity를 의미하며, 파란색 기호는 Dist 값을 의미합니다.
핵심은 서점과 사람 사이의 간선의 용량을 INF로 설정하는 것인데, 이것은 각 사람은 원하는만큼 책을 모두 구매할 수 있다는 조건이 보장되어야 하므로 사람과 SINK 사이의 Capacity를 Ai로, 서점과 사람 사이 간선의 Capacity를 INF로 설정해주어야 합니다.
결론적으로는 전반적으로 위와 같이 노드를 연결하여 그래프를 구성할 것입니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 205
#define INF 1000000000
#define SOUR 1
#define SINK 2
using namespace std;
int Capacity[MAX][MAX], Flow[MAX][MAX], SinDist[MAX][MAX];
vector<int> Line[MAX];
int MCMF(int Sour, int Sink) {
int CostSum = 0;
while(true) {
bool isInQueue[MAX] = {};
int Parent[MAX] = {}, Dist[MAX];
fill(Dist, Dist+MAX, INF);
Dist[SOUR] = 0;
queue<int> Queue;
Queue.push(Sour);
isInQueue[Sour] = true;
while(!Queue.empty()) {
int Cur = Queue.front();
Queue.pop();
isInQueue[Cur] = false;
for(int i=0; i<Line[Cur].size(); i++) {
int Next = Line[Cur][i];
if(Capacity[Cur][Next] - Flow[Cur][Next] > 0
&& Dist[Cur] + SinDist[Cur][Next] < Dist[Next]) {
Dist[Next] = Dist[Cur] + SinDist[Cur][Next];
Parent[Next] = Cur;
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*SinDist[Parent[i]][i];
Flow[Parent[i]][i] += Amount;
Flow[i][Parent[i]] -= Amount;
}
}
return CostSum;
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
for(int i=M+3; i<M+N+3; i++) {
Line[i].push_back(SINK), Line[SINK].push_back(i);
scanf("%d", &Capacity[i][SINK]);
}
for(int i=3; i<M+3; i++) {
Line[SOUR].push_back(i), Line[i].push_back(SOUR);
scanf("%d", &Capacity[SOUR][i]);
}
for(int i=3; i<M+3; i++) {
for(int j=M+3; j<M+N+3; j++) {
Line[i].push_back(j), Line[j].push_back(i);
Capacity[i][j] = INF;
scanf("%d", &SinDist[i][j]);
SinDist[j][i] = -SinDist[i][j];
}
}
printf("%d", MCMF(SOUR, SINK));
}
구현 자체는 일반적인 MCMF 알고리즘의 구현과 비슷하며, 이에 대해서는 BOJ 문제풀이 카테고리의 이전 포스트들에 설명해두었으니 참고하시면 좋을 것 같습니다.
위의 그림 설명에서 노드의 최댓값은 M+N+2이고 M과 N은 100 이하의 자연수이므로 MAX를 적절히 205 정도로 설정해주면 메모리를 최소에 가깝게 아낄 수 있습니다.
MCMF 알고리즘은 음의 간선을 고려하여 작동하는 알고리즘이므로, 간선의 비용을 설정해줄 때 음의 비용 역시 설정해 주는 것을 잊어버리면 안됩니다.
풀이 코드를 제출해보면 위와 같은 결과로 CA 처리를 받을 수 있습니다.
11406번 : 책 구매하기 2
11406번: 책 구매하기 2
총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각
www.acmicpc.net
위의 문제와 거의 같은 형식이지만 책을 보내는데 소모되는 비용은 없고, 대신 구매 가능한 최대 책의 수를 구하는 문제입니다.
이 문제는 오히려 이전 문제보다 쉬운 유형으로, MCMF 알고리즘이 아닌 일반적인 최대 유량 알고리즘을 사용해주면 됩니다.
정리해보면 위의 그림과 같이 Cost에 대한 설정은 전혀 해줄 필요 없이 Capacity에 대한 설정과 간선들의 연결만 적절히 해주면 MaxFlow 알고리즘으로 쉽게 해결이 가능합니다.
↓ 포스트의 길이가 너무 길어질 수 있으므로 풀이 코드는 아래의 접은 글에 정리해두었습니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 205
#define INF 1000000000
#define SOUR 1
#define SINK 2
using namespace std;
int Capacity[MAX][MAX], Flow[MAX][MAX];
vector<int> Line[MAX];
int MaxFlow(int Sour, int Sink) {
int Sum = 0;
while(true) {
int Parent[MAX] = {};
queue<int> Queue;
Queue.push(Sour);
while(!Queue.empty() && !Parent[Sink]) {
int Cur = Queue.front();
Queue.pop();
for(int i=0; i<Line[Cur].size(); i++) {
int Next = Line[Cur][i];
if(Capacity[Cur][Next] - Flow[Cur][Next] > 0 && !Parent[Next]) {
Queue.push(Next);
Parent[Next] = Cur;
}
}
}
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]) {
Flow[Parent[i]][i] += Amount;
Flow[i][Parent[i]] -= Amount;
}
Sum += Amount;
}
return Sum;
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
for(int i=M+3; i<M+N+3; i++) {
Line[i].push_back(SINK), Line[SINK].push_back(i);
scanf("%d", &Capacity[i][SINK]);
}
for(int i=3; i<M+3; i++) {
Line[SOUR].push_back(i), Line[i].push_back(SOUR);
scanf("%d", &Capacity[SOUR][i]);
}
for(int i=3; i<M+3; i++) {
for(int j=M+3; j<M+N+3; j++) {
Line[i].push_back(j), Line[j].push_back(i);
scanf("%d", &Capacity[i][j]);
}
}
printf("%d", MaxFlow(SOUR, SINK));
}
구현 역시 일반적인 네트워크 플로우의 구현과 동일하고, 배열의 최대 폭 역시 M+N+3 이상으로만 잡아주면 되므로 적절히 범위에 따라 205 정도로 MAX를 잡아주면 됩니다.
11407번 : 책 구매하기 3
위의 두 문제 책 구매하기 1과 2를 합친듯한 문제입니다.
서점에서 사람에게 책을 보낼 때의 Capacity의 제한도 존재하고, Cost 역시 동시에 존재합니다.
따라서 MCMF 알고리즘을 사용하되, 여기에 C_ij 값까지 그래프에 적용시켜서 문제를 해결해야 합니다.
그래프의 모식도를 그리면 위와 같이 되며, 구조 자체는 위의 문제들과 거의 비슷하니 설명은 생략하겠습니다.
↓ 포스트의 길이가 너무 길어지는 것을 막기 위해, 풀이 코드는 아래 접은 글에 정리해 두었습니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 205
#define INF 1000000000
#define SOUR 1
#define SINK 2
using namespace std;
int Count = 0, CostSum = 0;
int Capacity[MAX][MAX], Flow[MAX][MAX], SinDist[MAX][MAX];
vector<int> Line[MAX];
void MCMF(int Sour, int Sink) {
while(true) {
bool isInQueue[MAX] = {};
int Parent[MAX] = {}, Dist[MAX];
fill(Dist, Dist+MAX, INF);
Dist[SOUR] = 0;
queue<int> Queue;
Queue.push(Sour);
isInQueue[Sour] = true;
while(!Queue.empty()) {
int Cur = Queue.front();
Queue.pop();
isInQueue[Cur] = false;
for(int i=0; i<Line[Cur].size(); i++) {
int Next = Line[Cur][i];
if(Capacity[Cur][Next] - Flow[Cur][Next] > 0
&& Dist[Cur] + SinDist[Cur][Next] < Dist[Next]) {
Dist[Next] = Dist[Cur] + SinDist[Cur][Next];
Parent[Next] = Cur;
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*SinDist[Parent[i]][i];
Flow[Parent[i]][i] += Amount;
Flow[i][Parent[i]] -= Amount;
}
Count += Amount;
}
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
for(int i=M+3; i<M+N+3; i++) {
Line[i].push_back(SINK), Line[SINK].push_back(i);
scanf("%d", &Capacity[i][SINK]);
}
for(int i=3; i<M+3; i++) {
Line[SOUR].push_back(i), Line[i].push_back(SOUR);
scanf("%d", &Capacity[SOUR][i]);
}
for(int i=3; i<M+3; i++) {
for(int j=M+3; j<M+N+3; j++) {
Line[i].push_back(j), Line[j].push_back(i);
scanf("%d", &Capacity[i][j]);
}
}
for(int i=3; i<M+3; i++) {
for(int j=M+3; j<M+N+3; j++) {
scanf("%d", &SinDist[i][j]);
SinDist[j][i] = -SinDist[i][j];
}
}
MCMF(SOUR, SINK);
printf("%d\n%d", Count, CostSum);
}
풀이 코드에서 달라지는 부분은 두 가지입니다.
먼저 Capactiy를 반복문으로 입력받은 뒤 Single Dist 값을 다시 반복문으로 입력받아야 한다는 점, 그리고 Count(최대로 구매할 수 있는 책의 수)를 계산할 때 Amount가 한 번에 2 이상이 나올 수 있으므로 Count += Amount로 그 값을 갱신해주어야 한다는 점입니다.
나머지는 책 구매하기 1의 풀이 코드와 완전히 동일하므로, 설명은 생략하겠습니다.
'알고리즘 > 백준(BOJ) 문제풀이' 카테고리의 다른 글
| [C++ 백준 풀이] 15892번 : 사탕 줍는 로봇 / 17222번 : 위스키 거래 / 1258번 : 문제 할당 (0) | 2021.12.27 |
|---|---|
| [C++ 백준 풀이] 10976번 : 피난 / 17412번 : 도시 왕복하기 1 / 2316번 : 도시 왕복하기 2 (0) | 2021.12.27 |
| [C++ 백준 풀이] 2367번 : 파티 (최대 유량 알고리즘) (0) | 2021.12.26 |
| [C++ 알고리즘] 최소 비용 최대 유량 알고리즘 (MCMF 알고리즘) (0) | 2021.12.26 |
| [C++ 백준 풀이] 11377번 : 열혈강호 3, 11378번 : 열혈강호 4 (최대 유량 알고리즘) (0) | 2021.12.26 |