boj, 백준) 17412. 도시 왕복하기1 (C/C++)

1. 문제 링크

www.acmicpc.net/problem/17412

17412번: 도시 왕복하기 1

2. 문제 개요

N개의 도시가 P개의 단방향 길로 연결되어 있다. 1번 도시에서 시작해서 2번 도시로 가야 하는데, 한번 경로에 포함된 길은 다시 포함되어서는 안된다. 이때, 1번 도시에서 2번 도시까지 갈 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

단 한번만 가야 한다..라는 것의 의미를 다시 생각해보자. 한번 가고 나면 간선(경로, 도로)이 막히는 그런 게 있었던 것 같은데....

 

 

4. 문제 풀이

네트워크 유량문제이다.

에드몬드카프 알고리즘을 사용해서 최대 유량을 구하자.

(알고리즘 그 자체는 다른 분들께서 잘 정리해서 올렸으니 그걸 참조하면 되겠습니다.)

 

딱 한 번만 갈 수 있다. 그리고 단방향이다. 라는게 핵심.

딱 한번만 갈 수 있다는 간선의 용량을 1로 하면 됨을 의미하고,

단방향은 간선이 갖고 있는 방향으로만 용량을 할당하면 됨을 의미한다.

 

응용이 단 하나도 없는 네트워크 유량 문제이다. 도시 왕복하기 2 등을 풀어보며 조금씩 응용해보자.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, p, ans;
int flow[401][401];
int capacity[401][401];
vector<vector<int>> adj;
const int src = 1, dst = 2;

void edmonds_karp() {

	while (1)
	{
		queue<int> q;
		q.push(src);
		vector<int> parent(n + 1, -1);
		int minflow = 987654321;

		while (!q.empty()) {
			
			int cur = q.front(); q.pop();

			for (int next : adj[cur]) 
				if (capacity[cur][next] - flow[cur][next] > 0 && parent[next] == -1) {
					q.push(next);
					parent[next] = cur;
					if (next == dst)	break;
				}
		}

		if (parent[dst] == -1) break;

		for (int i = dst; i != src; i = parent[i]) 
			minflow = min(minflow, capacity[parent[i]][i] - flow[parent[i]][i]);
		
		for (int i = dst; i != src; i = parent[i])
		{
			flow[parent[i]][i] += minflow;
			flow[i][parent[i]] -= minflow;
		}
		ans += minflow;
	}

	return;
}

int main()
{
	scanf("%d %d", &n, &p);

	adj.resize(n + 1);

	for (int i = 0; i < p; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		adj[to].push_back(from);
		capacity[from][to] = 1;
	}

	edmonds_karp();

	printf("%d", ans);

	return 0;
}

 

 

6. 결과