[C++]백준16988번 Baaaaaaaaaduk2 (Easy)

문제는 다음과 같다.

오늘은 백준16988번 Baaaaaaaaaduk2 (Easy) 문제를 풀어보도록 하자. 처음 생각난건 바둑돌 2가지를 놓을 수 있는 경우의 수를 파악하는 것이라 조합을 생각했다. 따라서 조합을 구현하기 위해 DFS를 구현하였다.

그 후 생각이 막혔다. 조합을 이용해서 바둑알을 두었는데 상대의 바둑알을 어떻게 먹느냐를 구현해야했다. 한참을 생각하다가 격자점을 생각했다. 만일 격자점을 2번 이상 지나고 그 점이 상대의 돌이라면 먹을 수 있다고 생각했다.

하지만 완전한 오판이였다. 따라서 생각을 다시 한 번 해보았다. 과거 백준 치즈문제가 생각났다. 위 문제와는 다르게 겉표면을 탐색하는 문제였다.

따라서 위 문제는 반대로 갇혔을 때, 즉 상대의 돌부터 탐색을 해보면 어떨까? 라는 생각을 했고 풀 수 있었다. 지금까지 배웠던 BFS,DFS를 섞어서 구현할 수 있어야 했다. 재밌는 문제였고 다음에 다시 풀어볼만한 가치가 있는 문제였다.

                                     [코드]
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int map[20][20];
bool visit[20][20];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int R, C, answer = 0, temp = 0, q = 0;
queue<pair<int, int>>Q;

void Init_visit() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visit[i][j] = false;
		}
	}
}

void find_the_cnt(int i, int j) {
	bool flag = false;
	temp = 1;
	Q.push(make_pair(i, j));
	visit[i][j] = true;

	while (!Q.empty()) {
		int y = Q.front().first;
		int x = Q.front().second;

		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (my >= 0 && mx >= 0 && my < R && mx < C) {
				if (!visit[my][mx]) {
					if (map[my][mx] == 2) {
						visit[my][mx] = true;
						Q.push(make_pair(my, mx));
						temp++;
					}
					if (map[my][mx] == 0) {
						flag = true;
					}
				}
			}
		}
	}
	if (!flag) {
		q += temp;
	}
}

void select_the_one(int cnt) {
	if (cnt == 2) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (!visit[i][j] && map[i][j] == 2) {
					find_the_cnt(i, j);
				}
			}
		}
		answer = max(q, answer);
		q = 0;
		Init_visit();
		temp = 0;
		return;
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				select_the_one(cnt + 1);
				map[i][j] = 0;
			}
		}
	}
}

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

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}
	select_the_one(0);
	cout << answer;
}