백준 - 14502 연구소

 

1. 브루트포스를 이용한 벽 세우기

2. 그냥  bfs 

 

벽 세우기가 너무 어려웠다. 0 인 위치점을 전부 push_back 으로 기억한다. 이게 많이 중요했다.

0 의 위치점들을 전부 알고 있으니 3개의 벽에 차례대로 벽의 위치를 알려주면 "인덱스가 넘어갔을 때" 같은 생각 따윈 안해도 된다.

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

using namespace std;

vector<vector<int>> v2;
vector<vector<bool>> visited(100, vector < bool>(100, false));

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

struct Pos
{
	Pos() = default;
	Pos(int a, int b) : y(a), x(b)
	{

	}

	int x;
	int y;

	bool operator!= (const Pos& other)const
	{
		if (x == other.x)
		{
			if (y == other.y)
			{
				return false;
			}
		}
		return true;
	}

	bool operator== (const Pos& other)const
	{
		return !(*this != other);
	}

	bool operator<(const Pos& other)const
	{
		if (x != other.x)
		{
			return x < other.x;
		}
		return y < other.y;
	}
};

vector<Pos> zeros;
vector <Pos> two;

int main(void)
{
	
	int n, m;

	cin >> n >> m;

	vector<vector<int>> v(n , vector<int>(m));


	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			int num;
			cin >> num;
			v[i][j] = num;
			if (num == 0)
			{
				zeros.push_back(Pos(i, j));
			}
			else if (num == 2)
			{
				two.push_back(Pos(i, j));
			}
		}
	}
	int answer = 0;


	for (int i = 0; i < zeros.size(); ++i)
	{
		for (int j = i+1; j < zeros.size(); ++j)
		{
			for (int l = j+1; l < zeros.size(); l++)
			{
				v2 = v;

				for (int g = 0; g < v2.size(); ++g)
				{
					for (int h = 0; h < v2[g].size(); ++h)
					{
						visited[g][h] = false;
					}
				}
				
				// 벽 0 이 들어 있는 배열에서 가져옴
				v2[zeros[i].y][zeros[i].x] = 1;
				v2[zeros[j].y][zeros[j].x] = 1;
				v2[zeros[l].y][zeros[l].x] = 1;

				int fakeanswer = 0;


				queue<Pos> q;

				for (int k = 0; k < two.size(); ++k)
				{
					q.push(two[k]);
					visited[two[k].y][two[k].x] = true;
				}

				
				while (!q.empty())
				{
					Pos pos = q.front();
					q.pop();

					for (int p = 0; p < 4; ++p)
					{
						int y = pos.y + dy[p];
						int x = pos.x + dx[p];

						if (y < 0 || y >= v2.size() || x < 0 || x >= v2[0].size())
						{
							continue;
						}

						if (visited[y][x] == true)
						{
							continue;
						}

						if (v2[y][x] == 2 || v2[y][x] == 1)
						{
							continue;
						}

						q.push(Pos(y, x));
						v2[y][x] = 2;
						visited[y][x] = true;
					}
				}

				for (int g = 0; g < v2.size(); ++g)
				{
					for (int h = 0; h < v2[g].size(); ++h)
					{
						if (v2[g][h] == 0)
						{
							fakeanswer++;
						}
					}
				}
				if (answer < fakeanswer)
				{
					answer = fakeanswer;
				}
			}
		}
	}

	cout << answer;


	return 0;
}