[백준] 16988번 Baaaaaaaaaduk2 (Easy)

링크

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

16988번: Baaaaaaaaaduk2 (Easy)

풀이

 

현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 개수를 구하는 문제이다.

 

일단 Easy 버전은 n, m의 범위가 20 이하 이기 때문에 돌 2개를 놓을 수 있는 모든 경우에 대해 확인할 수 있는 완전 탐색을 이용할 수 있다.

 

그래서 next_permutation를 이용하여 빈 공간에 돌 2개를 놓을 수 있는 모든 경우의 수를 만들어

 

상대방 돌을 탐색하며 방문 체크를 해주고 탐색 중에 상대방 돌 옆에 빈공간이 한 개라도 있다면

check 변수를 false 로 만들어 빈 공간이 있다고 체크해주고 탐색 중에 빈 공간이 없었다면

sum 변수에 돌의 갯수를 더해 주었다.

 

매번 2개의 돌의 위치가 바뀌고 탐색이 완료된 후 검은 돌의 개수를 최대로 갱신하고 마지막에 출력을 해주었습니다.

 

 

그리고 상대방 돌을 탐색하며 빈 공간을 만났을 때에도 계속 이어진 상대방 돌을 탐색하며 방문 체크를 해주어 다음에는 탐색되지 않도록 했습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 25
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

int arr[SIZE][SIZE];
bool visited[SIZE][SIZE];
bool tmp[SIZE][SIZE];

vector<pair<int, int>> blank;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

int N, M;

bool check = true;

void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			tmp[i][j] = visited[i][j];
		}
	}
}

int dfs(int h_x, int h_y) {
	tmp[h_x][h_y] = true;
	int cnt = 1;
	for (int d = 0; d < 4; d++) {
		int n_x = h_x + dx[d];
		int n_y = h_y + dy[d];

		//범위 밖으로 나갈때, 이미 방문했을때, 내가 둔돌 일때
		if (n_x < 1 || n_x >N || n_y < 1 || n_y >M || tmp[n_x][n_y] == true || arr[n_x][n_y] == 1)
			continue;

		//빈 공간이 있을때
		if (arr[n_x][n_y] == 0) {
			check = false;
			continue;
		}
		
		cnt+= dfs(n_x, n_y);

	}
	return cnt;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) {
				blank.push_back({ i,j });
			}
		}
	}

	vector<int> ids(blank.size(), 0);
	for (int i = ids.size() - 2; i < ids.size(); i++) {
		ids[i] = 1;
	}
	
	int res = 0;
	do {
		init();

		for (int i = 0; i < ids.size(); i++) {
			if (ids[i] == 1) {
				tmp[blank[i].first][blank[i].second] = true;
			}
		}
	
		check = true;

		int sum = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (tmp[i][j] != true && arr[i][j] == 2) {
					int dfs_r= dfs(i, j);
					//빈공간을 만나지 않았다면 상대방돌을 더해줌
					if (check) {
						sum += dfs_r;
						
					}
				}	
				check = true;
			}
		}
		res = max(res, sum);
	} while (next_permutation(ids.begin(), ids.end()));
	

	cout << res;


}