Boj 2414) 구멍 채우기

문제

백준 2414

설명

돌멩이 제거 를 응용한 문제이다.

돌멩이 제거에서는 돌멩이의 좌표가 (x, y) 라고 하면 이 돌멩이를 X축의 x 와 Y축의 y을 잇는 간선이라고 생각할 수 있다. 우리는 모든 돌멩이와 연결되는 X,Y 축의 최소의 집합을 원한다. 그러면 문제는 모든 간선이 포함되는 최소의 정점을 찾는 Minimal Vertex Cover 문제가 된다. 그리고 이분매칭이므로 쾨닉의 정리로 최대 매칭되는 수를 찾는 문제가 된다.

여기서는 '.' 으로 가로막힌 부분은 구분이 되므로 같은 X, Y 좌표로 두면 안되고 구분을 시켜야한다. 구분하는 방법은 미리 X 축, Y 축 각각를 전처리하는 것인데, 아래 코드를 보면 간단히 이해할 수 있다. 어떻게 확장되는지 예제를 통해 알아보자.

4 4
*.*.
.***
***.
..*.

위 예제를 끊긴 구분을 구분한 좌표로 변환하면 다음처럼 나온다.

* . . . .
. . . * .
. . * * *
. * * * .
. . . * .

출력 코드는 다음과 같다.

	char realBoard[1000][1000];
	fill(realBoard[0], realBoard[1000], '.');
	for (int i = 0; i < x * y; i++)
		realBoard[yboard[i]-1][xboard[i]-1] = board[i];
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
			cout << realBoard[i][j] << ' ';
		cout << endl;
	}

시간 복잡도

O(\(VE\))

• n 을 기준으로 하면 O(\(n^3\))

코드

const int MAX_IN = 1001;
int n;
vector<int> lines[MAX_IN];
bool V[MAX_IN]; int B[MAX_IN];

bool DFS(int cur)
{
	if (V[cur]) return false;          // DFS 에서 visit 확인. 
	V[cur] = true;

	for (int l : lines[cur])
	{
		if (B[l] == 0 || DFS(B[l]))      // exposed vertex 가 나올때까지 dfs
		{
			B[l] = cur;
			return true;
		}
	}
	return false;
}

char board[51 * 51];
int xboard[51 * 51], yboard[51 * 51];

int main()
{
	fastio;
	int x, y;
	cin >> y >> x;

	for (int i = 0; i < x * y; i++)
		cin >> board[i];	
	
	int row = 0;
	for (int i = 0; i < y; i++)  // 같은 y 이지만 중간에 끊기면 다른 y 임
	{
		bool suc = false;
		for (int j = 0; j < x; j++)
		{
			if (board[i * x + j] == '*') {
				if (!suc) {
					suc = true; row++;
				}
				yboard[i * x + j] = row;
			}
			else suc = false;
		}
	}
	int col = 0;
	for (int i = 0; i < x; i++) // 같은 x 이지만 중간에 끊기면 다른 y 임
	{
		bool suc = false;
		for (int j = 0; j < y; j++)
		{
			if (board[j * x + i] == '*') {
				if (!suc) {
					suc = true; col++;
				}
				xboard[j * x + i] = col;
			}
			else suc = false;
		}
	}
	
	n = row;
	for (int i = 0; i < x * y; i++)
		if (yboard[i])
			lines[yboard[i]].push_back(xboard[i]);
	
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		fill(V, V + n + 1, 0);
		if (DFS(i)) ans++;
	}
	
	cout << ans;
}