[백준] 1420 학교 가지마! + 플로우 탬플릿

문제

도현이가 사는 도시는 N×M 크기의 모양이며, 1×1칸으로 나누어져 있다. 각 칸은 빈 칸 또는 벽이다.

도현이는 학교에 가려고 한다. 도현이가 있는 곳은 항상 빈 칸이고, 학교도 빈 칸에 있다. 도현이는 현재 있는 칸과 상하좌우로 인접한 칸으로 이동할 수 있다. 이때, 벽이 있는 칸으로는 이동할 수 없다. 또, 도시를 벗어날 수는 없다.

준규는 도현이가 학교에 가지 못하게 빈 칸을 적절히 벽으로 바꾸려고 한다. 이미 벽인 곳은 벽으로 바꿀 수 없고, 빈 칸만 벽으로 바꿀 수 있다. 도현이와 학교가 있는 곳은 벽으로 바꿀 수 없다.

도현이가 학교에 가지 못하게 하기 위해서 빈 칸을 벽으로 바꿔야하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. K와 H는 하나만 주어진다.

출력

첫째 줄에 도현이가 학교를 가지 못하게 하기 위해서 바꿔야 하는 벽의 최소 개수를 출력한다. 만약, 벽을 아무리 세워도 학교에 가는 것을 막을 수 없다면 -1을 출력한다.

 

한 정점과 다른 정점을 분리하는 최소 컷 문제입니다.

최소 컷 문제는 최대유량문제와 같습니다

에드먼드 카프 알고리즘을 사용합니다.

 

이 문제같은경우 한 정점에서 다른정점으로 갈 수 있는 방법이 여러개 이므로,

정점을 분리해야합니다.

 

정점을 분리하게 된다면,최대 100*100*2 개의 정점을 갖게되고, 각 정점에대해 capacity, flow 2차원배열을 만들어야하는데

(100*100*2)^2 크기의 배열은 만들 수 없습니다.

 

따라서 엣지 구조체를 만들어 각 정점당 간선을 부여하는 방식으로 문제를 풀 수 있습니다.

 

전처리가 상당히 까다롭습니다 ( 하 어지러워 )

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
//정점 구조체
struct Edge {
	//t: 목적지
	//c: capacity
	//f: flow
	int t, c, f=0;
	//생성자
	Edge(int to,int cap):t(to),c(cap){}

	//역간선 포인터
	Edge* rev;

	//capacity-flow
	int R() {
		return c - f;
	}
	//유량을 흘립니다
	void F(int a) {
		f += a;
		rev->f -= a;
	}
};
//간선을 만듭니다.
//간선은 양방향입니다 in>>out방향의 간선을 양쪽으로 두개만듭니다.
void AddEdge(int f_in, int f_out, int t_in, int t_out) {
	Edge* out_in=new Edge(t_in, INF);
	Edge* in_out = new Edge(f_out, 0);

	out_in->rev = in_out;
	in_out->rev = out_in;

	adj[f_out].push_back(out_in);
	adj[t_in].push_back(in_out);

	Edge* out_inc = new Edge(f_in, INF);
	Edge* in_outc = new Edge(t_out, 0);

	out_inc->rev = in_outc;
	in_outc->rev = out_inc;

	adj[t_out].push_back(out_inc);
	adj[f_in].push_back(in_outc);
}

int N, M, vnum, S, E;
char mp[102][102];
int v[202][202];
//정점의 크기는 N*M*2 입니다
vector<vector<Edge*>>adj(20004);


int MC() {
	int source = S + 1;
	int sink = E;
	int total_flow = 0;
	//에드먼드 카프 알고리즘
	while (1) {
		int p[20004];
		fill(p, p + 20004, -1);
		vector<Edge*> edge_to_child(20004);
		queue<int>q;
		q.push(source);
		p[source] = source;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (auto e : adj[cur]) {
				if (e->R() > 0 && p[e->t]==-1) {
					p[e->t] = cur;
					edge_to_child[e->t] = e;
					q.push(e->t);
				}
			}
		}
		if (p[sink] == -1)break;
		int flow = INF;
		for (int i = sink; i != source; i = p[i]) {
			Edge* ptoc = edge_to_child[i];
			flow = min(flow, ptoc->R());
		}
		for (int i = sink; i != source; i = p[i]) {
			edge_to_child[i]->F(flow);
		}
		total_flow += flow;
	}
	return total_flow;
}


int main() {
	FAST;
	cin >> N >> M;
	//간선
	//분할정점
	vnum = N * M * 2;
	//각 정점은 in>>out의 capacity 1 의 분할된 정점간 간선을 가지고 있습니다.
	//역간선도 있습니다.
	for (int i = 0; i < vnum; i += 2) {
		Edge* in_out = new Edge(i + 1, 1);
		Edge* out_in = new Edge(i, 0);

		in_out->rev = out_in;
		out_in->rev = in_out;

		adj[i].push_back(in_out);
		adj[i + 1].push_back(out_in);
	}
	int a, b;
	rep(i, N)rep(j, M) {
		cin >> mp[i][j];
		int v = (j + M * i)*2;
		if (mp[i][j] == 'K') {
			S = v;
			a = i, b = j;
		}
		if(mp[i][j]=='H'){
			E = v;
		}
	}
	//바로 옆에 붙어있나?
	rep(i, 4) {
		int ny = a + dy[i];
		int nx = b + dx[i];
		if (mp[ny][nx] == 'H') { cout << -1; return 0; }
	}
	rep(i, N)rep(j, M) {
		if (mp[i][j] == '#')continue;
		int v_in = (i * M + j) * 2; //i행j열 정점의 인덱스는 i*m + j로 만들 수 있습니다
		//다만 분할된 정점이므로 2를 곱해줍니다
		//out은 in+1입니다.
		int v_out = v_in + 1;
		v[i][j] = 1;
		rep(k, 4) {
			int ny = i + dy[k];
			int nx = j + dx[k];
			//정점간 간선을 만들어줍니다.
			if (ny >= 0 && ny < N && nx >= 0 && nx < M && mp[ny][nx] != '#' && !v[ny][nx]) {
				int t_in = (ny * M + nx) * 2;
				int t_out = t_in + 1;
				AddEdge(v_in, v_out, t_in, t_out);
			}
		}
	}
	cout << MC();
}

 

정점 구조체를 템플릿으로 저장해놓아야겠습니다..........

 

아직도 정점을 분할하는 경우와 정점을 분할하지 않는 경우를 구분하는게 헷갈리네요