Boj 1420) 학교 가지마!

문제

백준 1420

설명

정점 분할

K 와 H 를 막는 최소 컷을 구하는 것이 문제이다. 우리는 최대 유량 최소 컷 정리를 통해서 최대유량을 구하면 된다는 것을 알 수 있다. 이때 우리가 원하는건 정점인 벽을 최소한으로 없애는거지 간선의 수를 최소한으로 없애는 것이 아니다. 그러므로 정점 분할을 시도하여 정점을 간선으로 만들고 In->Out 의 Capacity 를 1 로 설정해야 한다. 그러면 간선이 아니라 정점을 최소한으로 막는 문제가 된다.

정점 분할을 시도하는 경우 기존의 정점 간의 간선의 Capacity 를 보통 무한대 값을 둔다. 여기서는 어차피 정점 분할로 정점 간 1 이상 흐르지 못하기 때문에 1로 둬도 상관없다.

시간복잡도에 대해서

100x100==10000 개의 정점에 간선이 대략 40000 개인데 에드몬크 카프 기준으로 어떻게 통과할 수 있을까? 이는 최대 흐름이 4로 (좌우상하를 막으면 되므로) 고정되어 있음을 생각하면 간단히 알 수 있다. 에드몬드 카프에서 Augmenting Path 에 대해 증가연산을 최대 \((\vert V \vert \vert E \vert)\) 번 하던 것이 4개로 줄기 때문에 증가연산을 위한 비용인 BFS 에 해당하는 O(\(\vert E\vert\)) 만 남기 때문이다.

관계행렬을 쓰면 메모리가 부족함

또 다른 문제는 메모리인데, 정점 당 5개의 간선만 (좌우상하 + 정점 분할용 간선) 가지는 걸 활용하면 정점->정점 의 관계를 (정점, 방향)->정점 으로 바꾸어 공간복잡도를 O(\(4NM\)) 으로 줄일 수 있다. 압축용 알고리즘은 Tricky 한데, 정점분할로 In-Out 으로 분리된 정점은 In 과 Out 간에만 연결이 되는 것과, 방향에 1,2,3,4 를 적당히 주면 5-dir 가 반대편 방향이 되는 것을 이용했다.

그냥 속편하게 unordered_map<int, unordered_map<int, int>> 를 사용해도 된다.

시간 복잡도

O(\((NM)^2\))

코드

const int MAX_IN = 20002;
char board[101 * 101];
int n, m;

int InID(int x, int y) { return (y * m + x + 1) * 2; }
int OutID(int x, int y) { return (y * m + x + 1) * 2 + 1; }
int Next(int v, int dir) {
	bool bOut = v % 2;
	if (dir == 0) return bOut ? v - 1 : v + 1;

	v /= 2;
	int x = v % m-1, y = v / m;
	
	if (bOut) { // out -> in
		switch (dir)
		{
		case 1: return InID(x-1, y); // left;
		case 2: return InID(x, y-1); // up;
		case 3: return InID(x, y+1); // down;
		case 4: return InID(x+1, y); // right;
		}
	}
	else { // in -> out
		switch (dir)
		{
		case 1: return OutID(x-1, y); // left;
		case 2: return OutID(x, y-1); // up;
		case 3: return OutID(x, y+1); // down;
		case 4: return OutID(x+1, y); // right;
		}
	}
}

vector<int> lines[MAX_IN];
int c[MAX_IN][5], f[MAX_IN][5]; pair<int,int> d[MAX_IN];
int T, S;
int Edmonds_Karps()
{
	int res = 0;
	while (1)
	{
		fill(d, d + MAX_IN, pair{ -1, -1 });

		queue<int> works;
		works.push(S);
		while (!works.empty())
		{
			int cur = works.front();
			works.pop();
	
			for (int l : lines[cur])
			{
				int next = Next(cur, l);
				if (c[cur][l] - f[cur][l] > 0 && d[next].first == -1)
				{
					d[next] = { cur, l };
					works.push(next);
				}
			}
		}
	
		if (d[T].first == -1) break;
	
		int add = 1e9;
		for (auto i = d[T]; i.first != S; i = d[i.first])
			add = min(add, c[i.first][i.second] - f[i.first][i.second]);
		for (auto i = d[T]; i.first != S; i = d[i.first])
		{
			f[i.first][i.second] += add;
			f[Next(i.first, i.second)][i.second > 0 ? 5 - i.second : 0] -= add;
		}
		res += add;
	}
	return res;
}

void Push(int x, int y, int dx, int dy, int dir)
{
	if (x + dx < 0 || x + dx >= m) return;
	if (y + dy < 0 || y + dy >= n) return;
	int dest = (y + dy) * m + x + dx;
	if (board[dest] == 'K' || board[dest] == '#') return;
	lines[OutID(x, y)].push_back(dir);
	lines[InID(x+dx, y+dy)].push_back(5-dir);
	c[OutID(x, y)][dir] = 1;
}

int main()
{
	fastio;

	cin >> n >> m;
	
	int H = 0, K = 0;
	for (int i = 0; i < n * m; i++)
	{
		cin >> board[i];
		if (board[i] == 'H') H = i;
		if (board[i] == 'K') K = i;
	}
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			// 정점 분할용 간선
			lines[InID(j, i)].push_back(0);
			lines[OutID(j, i)].push_back(0);
			c[InID(j, i)][0] = 1;
	
			// 좌우상하를 연결함
			char c = board[i * m + j];
			if (c == '#') continue;
			if (c == 'H') continue;
			Push(j, i, -1, 0, 1); // left
			Push(j, i, 0, -1, 2); // up
			Push(j, i, 0, 1,  3); // down
			Push(j, i, 1, 0,  4); // right
		}
	
	bool impossible = abs(H % m - K % m) + abs(H / m - K / m) <= 1;
	S = OutID(K % m, K / m); T = InID(H % m, H / m);
	cout << (impossible ? -1 : Edmonds_Karps());
}