백준, boj) 1867. 돌멩이 제거 ( C / C++)

1. 문제 링크

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

1867번: 돌멩이 제거

2. 문제 개요

한 번에 하나의 행이나, 하나의 열 중 하나를 골라서 정리할 때, 최소로 움직여서 모든 돌을 치우는 방법.

 

3. 문제 힌트

 최소 버텍스 커버 유형입니다.

 행의 집합, 열의 집합으로 이루어진 그래프는 이분 그래프의 모양을 띄고,

 간선(돌)을 모두 커버 할 수 있는 것.

 

4. 문제 풀이

처음에 문제를 봤을 때 최소 버텍스 커버 유형의 문제일 거라 예상했습니다만,

'간선'이 의미하는 바가 뭔지 명확하게 몰라 풀고 나서도 많이 생각했던 문제였습니다.

 

1번의 실행 단위가 행 or열입니다. 

(문제의 예제로 가정) 9개로 나뉘어있는 한 칸 한 칸을 정점이라 보지 말고

하나의 실행 단위인 행 과열을 정점으로 생각합시다. 그리고 간선을 돌멩이라고 생각해봅시다.

Vertex cover의 의미는 집합 S에서 부분집합 S`를 골랐을 때, 그 집합 S`가 모든 간선을 커버하는가를 의미합니다.

즉, 최소 버텍스 커버는 모든 간선(돌멩이)을 커버하느냐를 의미하고, 모든 돌멩이를 주울 수 있느냐로 바꿀 수 있습니다.

 

따라서 돌멩이가 있는 행, 열( i , j )은 i행 j열 정점을 연결해줍니다.

 

 

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int ans = 0;
int adj[501][501];
 
int group[2][501][501];
int groupcount[2] = { 0,0 };
 
int map[501][501];
int n, k;
bool visited[501];
int p[501];
 
bool dfs(int cur)
{
	if (visited[cur])
		return false;
	visited[cur] = true;
 
	for (int next = 0; next < groupcount[1]; ++next)
	{
		if (adj[cur][next] == 1){
			if (p[next] == -1 || dfs(p[next]))
			{
				p[next] = cur;
				return true;
			}
		}
	}
	return false;
}
 
 
int main()
{
	scanf("%d %d", &n, &k);
 
	for (int i = 0; i < k; ++i){
		int y, x;
		scanf("%d %d", &y, &x);
		map[y - 1][x - 1] = 1;
	}
	memset(group, -1, sizeof(group));
	memset(p, -1, sizeof(p));
 
	//가로 집합만들기
	for (int i = 0; i < n; ++i){
		
		for (int j = 0; j < n; ++j)
		{
			if (map[i][j] == 1)
				group[0][i][j] = groupcount[0];
		}
		groupcount[0]++;
	}
 
	for (int j = 0; j < n; ++j) {
 
		for (int i = 0; i < n; ++i)
		{
			if (map[i][j] == 1)
				group[1][i][j] = groupcount[1];
		}
		groupcount[1]++;
	}
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (map[i][j] == 1)
				adj[group[0][i][j]][group[1][i][j]] = 1;
 
	
	for (int i = 0; i < groupcount[0]; ++i)
	{
		memset(visited, false, sizeof(visited));
		if (dfs(i))
			ans++;
	}
	printf("%d", ans);
 
 
	return 0;
}

여기서는 인접 행렬을 사용했지만, 인접 리스트를 쓰는 것도 별로 어렵지 않습니다!!

 

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~