[BOJ] 2316 : 도시 왕복하기 2
💉문제 내용
💉입출력
🧺입력
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다.
🧺출력
첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다.
🔋예제 입출력
🔮예제 입력1
5 5
1 3
3 2
1 5
5 4
4 2
🔮예제 출력1
2
🔮예제 입력2
6 7
1 3
3 2
1 4
4 2
1 5
5 6
6 2
🔮예제 출력2
3
🔮예제 입력3
7 8
1 3
1 4
3 5
4 5
5 6
5 7
6 2
7 2
🔮예제 출력3
1
💉문제 분석
🔋분류
최대 유량, 네트워크 유량, 분할 정복
🔋난이도
플래티넘III
💉문제 풀이
🔋해법
🧺입력
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다.
🧺출력
첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다.
🔮예제 입력1
5 5
1 3
3 2
1 5
5 4
4 2
🔮예제 출력1
2
🔮예제 입력2
6 7
1 3
3 2
1 4
4 2
1 5
5 6
6 2
🔮예제 출력2
3
🔮예제 입력3
7 8
1 3
1 4
3 5
4 5
5 6
5 7
6 2
7 2
🔮예제 출력3
1
🔋분류
최대 유량, 네트워크 유량, 분할 정복
🔋난이도
플래티넘III
💉문제 풀이
🔋해법
우선은 이 문제는 네트워크유량과 분할정복을 사용하여 풀수있습니다.
네트워크유량 알고리즘함수쪽은 전혀건드리지않았구요, 이 문제에서는 분할 정복이라는것이 사용됩니다.
한 정점내에 다른정점으로부터 연결되오는 in과 다른정점으로 연결하는 out으로 정점을 분할하여 풀수있습니다.
우선은 in은 1~401까지 out은 402~801까지로 설정했습니다.
우선 1부터 N만큼의 정점이 존재합니다.
따라서, 정점의 갯수인 1부터 N의 정점들을 모두 in, out정점으로 분할하여 서로를 가리키도록하며, 이때 용량은 1이됩니다.
그리고 언제나 out정점이 in정점을 가리켜야하므로,
{a의 out} -> {b의 in}, {b의 in} -> {a의 out}
{b의 out} -> {a의 in}, {a의 in} -> {b의 out}
이런식으로 가리켜야하며, 이때 용량은 양방향으로 모두 1로 설정합니다.
마지막으로 시작지점은 1이아닌 OUT + 1이됩니다.
마찬가지로 현재 정점의 out이 다른정점의 in을 가리켜야하기때문이죠.
🔋소스코드
#include <iostream> //2316
#include <queue>
#include <vector>
#define MAX (802)
constexpr int OUT = 401;
constexpr int INF = 987654321;
std::vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX];
int networkFlow(int start, int end){
int ans = 0;
while(true){
std::vector<int> visit(MAX, -1);
std::queue<int>q;
q.push(start);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0;i<adj[x].size();++i){
int y = adj[x][i];
if(visit[y] == -1 && c[x][y] - f[x][y] > 0){
visit[y] = x;
q.push(y);
if(y == end) break;
}
}
}
if(visit[end] == -1) break;
int flow = INF;
for(int i = end;i!=start;i=visit[i]) flow = std::min(flow, c[visit[i]][i] - f[visit[i]][i]);
for(int i = end;i!=start;i=visit[i]){
f[visit[i]][i] += flow;
f[i][visit[i]] -= flow;
}
ans += flow;
}
return ans;
}
int main(){
std::cin.tie(0);
std::cout.tie(0);
std::ios_base::sync_with_stdio(0);
int N, P;
std::cin >> N >> P;
for(int i=1;i<=N;++i){
adj[i].push_back(OUT + i);
adj[OUT + i].push_back(i);
c[i][OUT + i] = 1;
}
for(int i=0;i<P;++i){
int a, b;
std::cin >> a >> b;
adj[OUT + a].push_back(b);
adj[b].push_back(OUT + a);
c[OUT + a][b] = 1;
adj[OUT + b].push_back(a);
adj[a].push_back(OUT + b);
c[OUT + b][a] = 1;
}
std::cout << networkFlow(OUT + 1, 2);
}
푸는시간은 40~50분정도 걸린것같습니다.
💉마치며...
이번 문제를 풀면서 저도 성장한것같네요..ㅎ
이 문제를 풀면서 분할정복이라는것도 배우게되었습니다.
알고리즘문제는 계속해서 꾸준히 풀면서 실력도 좋아졌으면 좋겠네요..!
궁금한 부분있으시면 댓글로 질문주세요~
Author And Source
이 문제에 관하여([BOJ] 2316 : 도시 왕복하기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dpmawile/boj2316저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)