[c++/백준 ] 14502번: 연구실

문제 링크

14502번: 연구실

풀이

브루트포스와 BFS를 이용하는 문제

1. 벽을 세 개 세워줘야 하는데 나는 빈 칸의 위치를 blank에 넣어주고,blank에서 조합으로 3개를 골라 벽을 세웠다.
2. 다른 BFS문제와 같이 queue를 이용해서 구현하였다.
   2-1. queue를 다 돌리고 연구소에 0 개수를 세서 max를 이용해 최댓값으로 갱신시킨다.

벽 세우는 과정에서 j랑 k를 1랑 2로 잘못 넣어서 조금 헤맸다 ...

코드

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

using namespace std;

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

int answer = 0;

void BFS(vector<vector<int>> arr)
{
	queue<pair<int, int>> q;
	vector<vector<int>> visit(arr.size(), vector<int>(arr[0].size()));
	for (int i = 0;i < arr.size();i++)
	{
		for (int j = 0;j < arr[i].size();j++)
		{
			if (arr[i][j] == 2)
			{
				q.push(make_pair(i, j));
				visit[i][j] = 1;
			}
		}
	}
	while (!q.empty())
	{
		int ny = q.front().first;
		int nx = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++)
		{
			int ty = ny + dy[i];
			int tx = nx + dx[i];
			if (ty < 0 || ty >= arr.size() || tx < 0 || tx >= arr[0].size()) continue;
			if (arr[ty][tx] == 1) continue;
			if (visit[ty][tx] == 1)continue;
			arr[ty][tx] = 2;
			visit[ty][tx] = 1;
			q.push(make_pair(ty, tx));
		}
	}

	int safe = 0;
	for (int i = 0;i < arr.size();i++)
	{
		for (int j = 0;j < arr[i].size();j++)
		{
			if (arr[i][j] == 0) safe++;
		}
	}
	//cout << safe << " ";
	answer=max(answer,safe);
}

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

	int n, m;
	cin >> n >> m;
	
	vector<vector<int>> origin;
	vector<pair<int, int>> blank;
	origin.resize(n, vector<int>(m));
	
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			int tmp;
			cin >> tmp;
			origin[i][j] = tmp;
			if (origin[i][j] == 0) blank.push_back(make_pair(i, j)); //빈칸인 것 찾기
		}
	}
	for (int i = 0;i < blank.size() - 2;i++) //벽 세우기
	{
		for (int j = i+1;j < blank.size() - 1;j++)
		{
			for (int k = j+1;k < blank.size();k++)
			{
				vector<vector<int>> arr;
				arr = origin;
				arr[blank[i].first][blank[i].second] = 1;
				arr[blank[j].first][blank[j].second] = 1;
				arr[blank[k].first][blank[k].second] = 1;
				BFS(arr);
			}
		}
	}


	cout << answer;
	

	return 0;
}