[BOJ 15892 // C++] 사탕 줍는 로봇

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

 

이번에 볼 문제는 백준 15892번 문제인 사탕 줍는 로봇이다.
문제는 아래 링크를 확인하자.

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

15892번: 사탕 줍는 로봇

이 문제는 각 방을 노드로, 복도의 사탕의 개수를 가중치로 하는 그래프로 나타냈을 때 1번 방과 N번 방을 각각 source와 sink로 하는 최대 유량을 구하는 것으로 풀 수 있다.

 

같은 한 쌍의 방을 둘 이상의 서로 다른 복도로 이을 수 있다는 점에 주의하자.

 

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

#define INF 1000000007
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int source, sink;
int edge[301][301];
vector<int> G[301];
int level[301];

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[301];

int dfs(int current, int flow) {
	if (current == sink) return flow;
	int cursize = G[current].size();
	for (int& i = turn[current]; i < cursize; i++) {
		int node = G[current][i];
		if (edge[current][node] && level[node] == level[current] + 1) {
			int f = dfs(node, min(edge[current][node], flow));
			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 N, M; cin >> N >> M;
	source = 1, sink = N;

	while (M--) {
		int x, y, w; cin >> x >> y >> w;
		if (edge[x][y]) {
			edge[x][y] += w;
			edge[y][x] += w;
		}
		else {
			edge[x][y] = edge[y][x] = w;
			G[x].push_back(y);
			G[y].push_back(x);
		}
	}

	int flow = 0;

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

	cout << flow;
}