[BOJ 17412] 도시 왕복하기 1

https://www.acmicpc.net/problem/17412

17412번: 도시 왕복하기 1

 

- 문제 요약

 

N개의 도시가 P개의 단방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 가며 워해머를 한다. 성실한 이석원은 1번에서 2번으로 가는 서로 다른 경로를 최대한 많이 찾으려고 하는데, 이때 한 경로에 포함된 길이 다른 경로에 포함되면 안된다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다. 1번에서 2번으로 가는 서로 다른 경로의 최대 개수를 출력하시오.

 

 

- 알고리즘 정리

 

"이때 한 경로에 포함된 길이 다른 경로에 포함되면 안된다."라는 문장을 보고 바로 최대 유량 알고리즘을 떠올렸습니다. 에드몬드-카프 알고리즘(Edmonds-Karp Algorithm)을 활용했습니다.

 

문제에서 도시 간의 비용을 따로 지정해주지 않았기 때문에 비용은 1로 고정하고, 1번에서 2번 도시까지 가는 서로 다른 경로의 최대 개수를 출력해야 하므로, 시작점은 1, 끝점은 2로 설정하여 기본 알고리즘 형태로 돌려주기만 하면 됩니다.

 

 

- 코드 작성

 

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

#define MAX 401
int cap[MAX][MAX],flow[MAX][MAX],p[MAX];

void bfs(int s,int w){
	int start,dest;
	queue<int>q;
	q.push(s);
	for(int i=1;i<=MAX;i++){
		p[i]=-1;
	}
	while(!q.empty()){
		start=q.front();
		q.pop();
		for(dest=1;dest<=MAX;dest++){
			if(cap[start][dest]-flow[start][dest]>0&&p[dest]<0){
				q.push(dest);
				p[dest]=start;
				if(dest==w){
					return;
				}
			}
		}
	}
}

void f(int s,int w){
	int result=0;
	while(true){
		bfs(s,w);
		if(p[w]<0){
			break;
		}
		for(int i=w;i!=s;i=p[i]){
			flow[p[i]][i]+=1;
			flow[i][p[i]]-=1;
		}
		result++;
	}
	cout<<result;
}

int main(){
	int v,e,v1,v2;
	cin>>v>>e;
	for(int i=0;i<e;i++){
		cin>>v1>>v2;
		cap[v1][v2]=1;
	}
	f(1,2);
}

코드 제출 결과