백준 16988

문제링크

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

문제

풀이

모든 경우의 수를 생각하여 bfs를 돌려주며 풀었다.
크게 해야하는 작업은 다음의 두가지 이다.

1. 내 돌을 놓은 두 자리를 찾아서 돌을 놓아보기

   • 백트래킹과 next_permutation 알고리즘을 이용하여 놓을 두 자리를 골라낼 수 있다.

   • 아래 코드에서는 next_permutation을 이용했다.

2. 놓은 돌을 기준으로 현재의 바둑판에서 딸 수 있는 돌이 몇개인지 세기

   • 1번에서 돌을 놓은 각 경우에 대해 현재 바둑판의 상태에서 딸 수 있는 돌이 몇개인지 count를 해주었다.

   • 카운트 하는 방법은 맵을 훑으면서 적의 돌인 경우 큐에 집어넣고 bfs를 돌려준다.

   • bfs를 돌리는 과정에서 적의 돌에 빈공간(0)이 인접한 경우가 있었다면 0을 return 해준다.

   • 그렇지 않다면 세준 돌의 개수를 return 해준다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct {
	int x;
	int y;
}pos;
int n, m, ans;
int maps[21][21];
bool vi[21][21];
queue<pos> q;

int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };

int bfs(int x, int y, int type) {

	int cnt = 1;
	int check = 1;
	q.push({ x,y });
	vi[x][y] = true;

	while (!q.empty()) {
		int nowx = q.front().x;
		int nowy = q.front().y;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextx = nowx + dx[i];
			int nexty = nowy + dy[i];

			if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
			if (!vi[nextx][nexty]) {
				if (maps[nextx][nexty] == 0) check = 0;
				else if (maps[nextx][nexty] == type) {
					q.push({ nextx,nexty });
					vi[nextx][nexty] = true;
					cnt++;
				}
			}
		}
	}

	if (check) return cnt;
	else return 0;

}

int simulation() {
	fill(&vi[0][0], &vi[20][21], false);

	int total_cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] == 2 && !vi[i][j]) {
				total_cnt += bfs(i, j, maps[i][j]);
			}
		}
	}

	return total_cnt;
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

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


	vector<int> sel;
	for (int i = 0; i < n * m - 2; i++) sel.push_back(0);
	for (int i = 0; i < 2; i++) sel.push_back(1);

	do {
		vector<pos> selected;
		for (int i = 0; i < sel.size(); i++) {
			if (sel[i] == 1) {
				int x = i / m;
				int y = i % m;
				if (maps[x][y] == 0) selected.push_back({ x,y });
			}
		}

		if (selected.size() == 2) {
			for (int i = 0; i < 2; i++) maps[selected[i].x][selected[i].y] = 1;
			ans = max(ans, simulation());
			for (int i = 0; i < 2; i++) maps[selected[i].x][selected[i].y] = 0;
		}

	} while (next_permutation(sel.begin(), sel.end()));

	cout << ans;

}

후기

익숙한 유형이라 빨리 풀려고 하다보니까 코드가 난잡해지는것 같다.