취미로 코딩하기

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

이번에 볼 문제는 백준 5406번 문제인 No Smoking, Please이다.
문제는 아래 링크를 확인하자.

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

레스토랑의 출입구와 주방을 각각 source와 sink로 두고 각 방들을 노드로, 두 방을 잇는 연결통로를 각 방에 해당하는 두 노드를 이으면서 가중치가 (해당 통로에 air lock과 hatch를 설치할 때 필요한 비용)인 에지로 모델링을 하여 minimal cut을 구하면 문제를 해결할 수 있다.

벽에는 hatch가 필요없다는 조건이 레스토랑 전체를 나타내는 전체 직사각형의 바깥둘레를 의미하는 것으로 잘못 해석하여 매우 많은 오답을 제출했다(...). (연결통로의 크기가 0이라면 통로가 없으니 벽으로 생각해야하는 듯하다.)

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

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

int R, C, RC;
int source, sink;
int edge[1000000][4];
vector<int> G[1000000];
int level[1000000];

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]) {
			int n;
			if (node == 0) n = current - C;
			else if (node == 1) n = current + C;
			else if (node == 2) n = current - 1;
			else n = current + 1;
			if (edge[current][node] && level[n] == 0) {
				level[n] = level[current] + 1;
				que.push(n);
			}
		}
	}

	return level[sink];
}

int turn[1000000];

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];
		int n;
		if (node == 0) n = current - C;
		else if (node == 1) n = current + C;
		else if (node == 2) n = current - 1;
		else n = current + 1;
		if (edge[current][node] && level[n] == level[current] + 1) {
			int f = dfs(n, min(edge[current][node], flow));
			if (f) {
				edge[current][node] -= f;
				if (node == 0) edge[n][1] += f;
				else if (node == 1) edge[n][0] += f;
				else if (node == 2) edge[n][3] += f;
				else edge[n][2] += f;
				return f;
			}
		}
	}
	return 0;
}

void solve() {
	cin >> R >> C; RC = R * C;
	for (int i = 0; i < RC; i++) G[i].clear();
	memset(edge, 0, sizeof(edge));
	int sr, sc; cin >> sr >> sc; source = sr * C + sc;
	int tr, tc; cin >> tr >> tc; sink = tr * C + tc;
	for (int r = 0; r < R; r++) {
		for (int c = 1; c < C; c++) {
			int w; cin >> w;
			if (w) {
				w = w * 1000 + 1000;
				edge[r * C + c][2] = w;
				edge[r * C + c - 1][3] = w;
				G[r * C + c].push_back(2);
				G[r * C + c - 1].push_back(3);
			}
		}
	}
	for (int r = 1; r < R; r++) {
		for (int c = 0; c < C; c++) {
			int w; cin >> w;
			if (w) {
				w = w * 1000 + 1000;
				edge[r * C + c][0] = w;
				edge[(r - 1) * C + c][1] = w;
				G[r * C + c].push_back(0);
				G[(r - 1) * C + c].push_back(1);
			}
		}
	}
	
	int flow = 0;

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

	cout << flow << '\n';
}

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

	int T; cin >> T;
	while (T--) {
		solve();
	}
}