[백준/BOJ] 백준 16988번 : Baaaaaaaaaduk2 (Easy)

www.acmicpc.net/problem/16988

16988번: Baaaaaaaaaduk2 (Easy)

board에 2개의 돌을 놓을 수 있는 경우를 모두 확인해서 상대의 돌이 가장 많이 죽는 경우를 구했다. 상대의 돌은 그룹별로 묶어서 저장을 하고, 2개의 돌을 놓았을 때 없어지는 그룹들을 확인해 그 그룹들의 돌의 개수를 세서 총 죽는 돌의 개수를 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n, m;
int board[20][20];
vector<vector<pair<int, int>>> area; //상대돌의 그룹 정보를 저장
int check[20][20];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Pre()
{
	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			check[i][j] = 0;
}

void areaCheck(pair<int,int> here, vector<pair<int,int>>& this_area)
{
	this_area.push_back(here);
	check[here.first][here.second] = 1;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == 2 && check[there.first][there.second] == 0)
		{
			areaCheck(there, this_area);
		}
	}
}

//상대돌의 그룹을 저장한다
void areaFind()
{
	Pre();

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == 2 && check[i][j] == 0)
			{
				vector<pair<int, int>> this_area;
				areaCheck(make_pair(i, j), this_area);
				area.push_back(this_area);
			}
		}
}

int erase_areaCheck(vector<pair<int, int>>& selected)
{
	int ret = 0;

	//board에 selected 돌을 놓아본다
	for (int i = 0; i < selected.size(); i++)
		board[selected[i].first][selected[i].second] = 1;

	//상대돌의 그룹중 죽는 그룹이 되는것을 확인
	for (int i = 0; i < area.size(); i++)
	{
		bool this_area_erase = true;

		for (int j = 0; j < area[i].size(); j++)
		{
			for (int dir = 0; dir < 4; dir++)
			{
				pair<int, int> area_ij_dir = make_pair(area[i][j].first + dxdy[dir][0], area[i][j].second + dxdy[dir][1]);

				//이 그룹이 죽지 않을때
				if (area_ij_dir.first >= 0 && area_ij_dir.first < n && area_ij_dir.second >= 0 && area_ij_dir.second < m && board[area_ij_dir.first][area_ij_dir.second] == 0)
				{
					this_area_erase = false;
					break;
				}
			}

			if (this_area_erase == false)
				break;
		}

		//이 그룹이 죽게될때
		if (this_area_erase == true)
			ret += area[i].size();
	}

	//board에 놓았던 selected 돌을 다시 제거한다
	for (int i = 0; i < selected.size(); i++)
		board[selected[i].first][selected[i].second] = 0;

	return ret;
}

int Solve(vector<pair<int, int>>& selected, pair<int, int> last_selected)
{
	int ret = -1;

	//돌을 놓을 2곳을 골랐을때
	if (selected.size() == 2)
	{
		return erase_areaCheck(selected);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//i*m + j > last_selected.first*m + last_selected.second는 돌 놓을곳을 중복되게 선택하지 않기 위한 조건
			if (i*m + j > last_selected.first*m + last_selected.second && board[i][j] == 0)
			{
				selected.push_back(make_pair(i, j));
				ret = max(ret, Solve(selected, make_pair(i, j)));
				selected.pop_back();
			}
		}
	}

	return ret;
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;

	cin >> n >> m;

	for(int i=0; i<n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> input;
			board[i][j] = input;
		}

	areaFind(); //상대돌의 그룹을 찾는다

	vector<pair<int,int>> selected;
	cout << Solve(selected, make_pair(-1, -1));

	return 0;
}