[BOJ] 16988: Baaaaaaaaaduk2 (Easy)

 

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

16988번: Baaaaaaaaaduk2 (Easy)

 

가끔씩 있는 서론이 긴 문제다.

이런거 읽는것도 소소한 재미 중 하나

 

브루트포스로 풀었을 때 놓을 위치 두 가지를 선택하는 것은 O((NM)^2)이고, BFS(물론 DFS로 구현해도 된다)를 통해 바둑판 위의 돌들에 대해 죽었는지 아닌지를 판단하는 건 O(NM)의 시간 복잡도가 든다.

 

N과 M이 최대 20으로 작기 때문에, O((NM)^3)의 시간복잡도를 가지는 이 알고리즘은 입력이 최대인 경우 400^3 = 64,000,000으로 시간 안에 풀 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

int N, M;
int B[20][20];

int dr[] = { 1, 0, -1, 0 };
int dc[] = { 0, 1, 0, -1 };
bool visit[20][20];

bool isValid(int r, int c) {
	return (r >= 0) && (r < N) && (c >= 0) && (c < M);
}

int bfs(int r, int c) {
	using namespace std;

	queue<pair<int, int>> bfsOrder;
	bfsOrder.push(make_pair(r, c));
	visit[r][c] = true;

	int numOfStones = 0;
	bool isDead = true;

	while (!bfsOrder.empty()) {
		int nr = bfsOrder.front().first;
		int nc = bfsOrder.front().second;
		++numOfStones;
		bfsOrder.pop();
		for (int i = 0; i < 4; ++i) {
			int tempR = nr + dr[i], tempC = nc + dc[i];
			if (!isValid(tempR, tempC)) continue;
			if (B[tempR][tempC] == 0)
				isDead = false;

			if (!visit[tempR][tempC] && (B[tempR][tempC] == 2)) {
				bfsOrder.push(make_pair(tempR, tempC));
				visit[tempR][tempC] = true;
			}
		}
	}

	return isDead ? numOfStones : 0;
}

int getDeathCount() {
	int ret = 0;
	std::fill(&visit[0][0], &visit[N - 1][M], false);

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (!visit[i][j] && (B[i][j] == 2)) {
				ret += bfs(i, j);
			}
		}
	}

	return ret;
}

int main() {
	std::cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			std::cin >> B[i][j];
		}
	}

	int ret = -1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (B[i][j] == 0) {
				B[i][j] = 1;
				for (int k = 0; k < N; ++k) {
					for (int l = 0; l < M; ++l) {
						if (((i == k) && (j == l)) || (B[k][l] > 0)) continue;
						B[k][l] = 1;
						ret = std::max(ret, getDeathCount());
						B[k][l] = 0;
					}
				}
				B[i][j] = 0;
			}
		}
	}
	std::cout << ret;

	return 0;
}