취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10976번 문제인 피난이다.
문제는 아래 링크를 확인하자.

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

문제 조건에 따라 체크포인트를 노드로 하고 길을 방향이 있는 에지로 하는 그래프를 그리면 체크포인트 1에서 체크포인트 N으로 가는 그래프(DAG)를 얻을 수 있다.

이 그래프에서 출발점과 도착점을 각각 source와 sink로 보고, source 또는 sink와 연결된 간선의 가중치를 1로, 나머지 에지의 가중치를 INF로 하고 source에서 sink로 가는 maximum flow를 계산하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int source = 1, sink;
vector<int> G[201];
int edge[201][201];
int level[201];

bool bfs() {
	memset(level, 0, sizeof(level));
	level[source] = 1;
	queue<int> que;
	que.push(source);

	while (!que.empty()) {
		int current = que.front(); que.pop();
		for (auto node : G[current]) {
			if (edge[current][node] && level[node] == 0) {
				level[node] = level[current] + 1;
				que.push(node);
			}
		}
	}

	return level[sink];
}

int turn[201];

int dfs(int current, int flow) {
	if (current == sink) return flow;
	int gcursize = G[current].size();
	for (int& i = turn[current]; i < gcursize; i++) {
		int node = G[current][i];
		if (edge[current][node] && level[node] == level[current] + 1){
			int f = dfs(node, min(flow, edge[current][node]));
			if (f) {
				edge[current][node] -= f;
				edge[node][current] += f;
				return f;
			}
		}
	}

	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		memset(edge, 0, sizeof(edge));
		int N, M; cin >> N >> M;
		sink = N;
		while (M--) {
			int x, y; cin >> x >> y;
			if (x > y) swap(x, y);
			G[x].emplace_back(y);
			G[y].emplace_back(x);
			if (x == 1 || y == N) edge[x][y] = 1;
			else edge[x][y] = 1000000007;
		}

		int ans = 0;
		while (bfs()) {
			memset(turn, 0, sizeof(turn));
			int f;
			while (f = dfs(source, 1000000007)) ans += f;
		}

		cout << ans << '\n';
	}
}