백준(BOJ) 16988번 Baaaaaaaaaduk2 (Easy)

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

16988번: Baaaaaaaaaduk2 (Easy)

풀이 :

 

우선 좌표값이 0인 좌표들만 v 배열에 넣는다. 그 후 2개씩 뽑아서 각각의 경우를 확인한다.

 

좌표값이 2인 좌표를 고른 후 BFS를 통해 탐색해주는데 이때 각 좌표들은 모두 1로 둘러싸여

 

있어야 한다. 이 조건은 상하좌우가 0이 아니라는 조건과 일치하기 때문에 만약 0이 나온다면

 

bool 조건을 false로 주어서 더하지 못하게 막아준다.

 

코드 ( C++ )

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstring>
	#include <queue>
	using namespace std;
	int a[20][20];
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	int n, m;
	int best;
	int d[20][20];
	int bfs()
	{
	memset(d, 0, sizeof(d));
	int ret = 0;
	for(int i=0; i<n; ++i)
	for (int j = 0; j < m; ++j)
	{
	if (a[i][j] == 2 && d[i][j] == 0) {
	bool isDead = true;
	queue<pair<int, int>> q;
	q.push({ i,j });
	d[i][j] = 1;
	int num = 0;
	while (!q.empty())
	{
	num++;
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for (int k = 0; k < 4; ++k)
	{
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) continue;
	if (a[ny][nx] == 0)
	isDead = false;
	else if (a[ny][nx] == 2 && d[ny][nx] == 0) {
	d[ny][nx] = 1;
	q.push({ ny,nx });
	}
	}
	}
	if (isDead) {
	ret += num;
	}
	}
	}
	return ret;
	}
	int main()
	{
	vector<pair<int, int>> v;
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j)
	{
	cin >> a[i][j];
	if (a[i][j] == 0) {
	v.push_back({ i,j });
	}
	}
	int ans = 0;
	for (int i = 0; i < v.size(); ++i)
	for (int j = 0; j < v.size(); ++j)
	{
	if (i == j) continue;
	int fy = v[i].first;
	int fx = v[i].second;
	int sy = v[j].first;
	int sx = v[j].second;
	a[fy][fx] = 1;
	a[sy][sx] = 1;
	int cand = bfs();
	if (ans < cand)
	ans = cand;
	a[fy][fx] = 0;
	a[sy][sx] = 0;
	}
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub