이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 10976번 : '피난', 17412번 : '도시 왕복하기 1', 2316번 : '도시 왕복하기 2' 문제의 풀이 코드와 해설을 다루고 있습니다.
문제 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘에 대한 이해가 필요합니다.
10976번 : 피난
10976번: 피난
어느 날, CC동산에 놀러온 초등학생 석주가 CC동산에 무차별적으로 침을 뱉었다. CC동산 일대에서 열심히 일하던 개미들의 90%가 석주의 침 때문에 몰살당했고, 소수 개미와 1000마리의 여왕개미만
www.acmicpc.net
위의 규칙대로 개미를 보내는 과정은 유량을 보내는 과정과 똑같이 생각할 수 있으므로 적절한 그래프를 연결하여 최대 유량 알고리즘을 사용해주면 되는 문제입니다.
↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 205
#define INF 1000000000
#define SOUR 1
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 T, N, M, A, B;
scanf("%d", &T);
for(int t=0; t<T; t++) {
fill(&Capacity[0][0], &Capacity[MAX-1][MAX], 0);
fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]);
scanf("%d %d", &N, &M);
int SINK = N;
for(int i=0; i<M; i++) {
scanf("%d %d", &A, &B);
Line[A].push_back(B), Line[B].push_back(A);
if(A == 1 || B == N) Capacity[A][B] = 1;
else Capacity[A][B] = INF;
}
printf("%d\n", MaxFlow(SOUR, SINK));
}
}
1번 노드가 Sour, N번 노드가 Sink인 것만 인지하면 나머지 노드들은 주어진 연결대로 적절히 배치하여 구현하면 됩니다.
풀이를 제출해보면 위와 같이 정답 처리를 받을 수 있습니다.
17412번 : 도시 왕복하기 1
17412번: 도시 왕복하기 1
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.
www.acmicpc.net
문제 자체는 1번 노드와 2번 노드를 왕복하는 것이라고 했지만, 최대 유량 알고리즘을 응용하여 해결이 가능합니다.
모든 노드와 노드 사이의 간선의 용량을 1로 제한하고, 필요한 경로를 찾아 유량을 보내주는 과정을 반복하며 Count를 세어주면 두 도시를 왕복할 수 있는 횟수를 구할 수 있습니다.
↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 405
#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 Count = 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;
}
Count++;
}
return Count;
}
int main() {
int N, M, A, B;
scanf("%d %d", &N, &M);
for(int i=0; i<M; i++) {
scanf("%d %d", &A, &B);
Line[A].push_back(B), Line[B].push_back(A);
Capacity[A][B] = 1;
}
printf("%d", MaxFlow(SOUR, SINK));
}
구현 자체는 일반적인 네트워크 플로우 알고리즘과 같으며, sour = 1과 sink = 2에 유의하고 또 모든 간선의 용량을 1로 설정해주어야 한다는 점을 조심해야 합니다.
2316번 : 도시 왕복하기 2
2316번: 도시 왕복하기 2
N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방
www.acmicpc.net
위의 문제와 비슷해보이지만, 여기서는 한 번 방문한 노드를 다시 방문하지 못하도록 하는 조건이 추가되어 있습니다.
이러한 조건을 어떻게 구현할 수 있을지 생각해봅시다.
현재 문제의 핵심은 (1번과 2번 노드를 제외하고) 한 번 지나간 노드를 다시 지나갈 수 없도록 어떤 장치를 마련하는 것입니다.
우리는 노드에 대해서는 제한을 설정하기 힘들지만 (visit 배열을 쓰는 방법도 있을 것 같지만 더욱 간단하게 구현하기 위해) 유량이 1인 간선에 대해서는 다시 지나갈 수 없음을 알고 있습니다.
따라서 이를 이용하여 하나의 노드를 둘로 분할하고 이들 사이에 용량이 1인 간선을 설정하여, 한 번 지나간 간선은 다시 지나가지 못하도록 조건을 만들어주는 것입니다.
↓ 풀이 코드는 아래 접은 글에 정리되어 있습니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 805
#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 Count = 0;
while(true) {
int Parent[MAX] = {};
queue<int> Queue;
Queue.push(Sour);
Parent[Sour] = 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(Next == Sink) break;
}
}
}
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;
}
Count++;
}
return Count;
}
int main() {
int N, M, A, B;
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++) {
Line[i].push_back(i+N), Line[i+N].push_back(i);
Capacity[i][i+N] = 1;
}
for(int i=0; i<M; i++) {
scanf("%d %d", &A, &B);
Line[A+N].push_back(B), Line[B].push_back(A+N);
Line[A].push_back(B+N), Line[B+N].push_back(A);
Capacity[A+N][B] = Capacity[B+N][A] = INF;
}
printf("%d", MaxFlow(SOUR+N, SINK));
}
구현 방식은 거의 비슷하나, 번호를 쉽게 매기기 위해 저의 경우에는 특정 노드의 번호와 특정 노드 번호 + N으로 쪼개어 분할했고, 이 때 MAXN은 2N이 됨을 알 수 있습니다.
그리고 Capacity의 경우 특정 노드의 out 노드와 다른 노드의 in 노드 사이에는 INF로 설정해주어야 모든 경로를 찾을 수 있음에 주의해야 합니다. (용량을 1로 설정하는 것은 동일한 노드의 in과 out 노드 사이)
'알고리즘 > 백준(BOJ) 문제풀이' 카테고리의 다른 글
| [C++ 백준 풀이] 1585번 : 경찰 / 2365번 : 숫자판 만들기 (MCMF + 최대 유량 알고리즘) (0) | 2021.12.27 |
|---|---|
| [C++ 백준 풀이] 15892번 : 사탕 줍는 로봇 / 17222번 : 위스키 거래 / 1258번 : 문제 할당 (0) | 2021.12.27 |
| [C++ 백준 풀이] 11405~11407번 : 책 구매하기 1~3 (최대 유량 + MCMF 알고리즘) (0) | 2021.12.26 |
| [C++ 백준 풀이] 2367번 : 파티 (최대 유량 알고리즘) (0) | 2021.12.26 |
| [C++ 알고리즘] 최소 비용 최대 유량 알고리즘 (MCMF 알고리즘) (0) | 2021.12.26 |