[BFS, 난이도 중] 백준 14502번 연구소

 

 

내 접근 법은 연구실 지도에서 빈칸인 좌표를 모두 v벡터 안에 넣고 벽을 세울 3곳의 좌표를 고르는 모든 경우의 수를 탐색하는 것이다.

브루트포스와 짬뽕인 문제인것같다.

지도의 크기가 최대 8x8 이라 순열을 이용하여 모두 탐색해도 시간 초과는 나지 않는다.

모든 케이스마다 casemap 배열을 초기 map과 같게 해주고

바이러스가 들어있는 좌표를 모은 큐도 다시 채워줘야 한다.

a=v.size()-3

b=v.size()-2

c=v.size()-1 일 때는 모든 경우를 탐색했다는 뜻이므로 break문으로 빠져나와서, 안전 구역의 넓이의 최댓값을 출력하면 된 문제가 해결된다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int map[9][9];
int casemap[9][9];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int maxi(int a,int b){
    if(a>b)return a;
    else return b;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
    int ans=0;
	queue<pair<int, int> > q;
    vector<pair<int,int> > virus;
    vector<pair<int,int> > v;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
            if(map[i][j]==0){
                v.push_back(make_pair(i,j));
            }
            else if(map[i][j]==2){
                q.push(make_pair(i,j));
                virus.push_back(make_pair(i,j));
            }
        }
	}
    int a=0; int b=1; int c=2;
    while(1){
        for(int x=0;x<n;x++){
            for(int y=0;y<m;y++){
                casemap[x][y]=map[x][y];
            }
        }
        pair<int,int> wall1 = v[a];
        pair<int,int> wall2 = v[b];
        pair<int,int> wall3 = v[c];
        casemap[wall1.first][wall1.second]=1;
        casemap[wall2.first][wall2.second]=1;
        casemap[wall3.first][wall3.second]=1;

        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                if (x + dx[i] < 0 || x + dx[i] >= n || y + dy[i] < 0 || y + dy[i] >= m) continue;
                if (casemap[x + dx[i]][y + dy[i]] == 0) {
                    casemap[x + dx[i]][y + dy[i]] = 2;
                    q.push(make_pair(x + dx[i], y + dy[i]));
                }
            }
        }
        int safearea=0;
        for(int x=0;x<n;x++){
            for(int y=0;y<m;y++){
                if(casemap[x][y]==0) safearea++;
            }
        }
        ans = maxi(ans,safearea);
        safearea=0;
        for(int i=0;i<virus.size();i++) q.push(virus[i]);
        if(a==v.size()-3 && b==v.size()-2 && c==v.size()-1) break;
        if(c!=v.size()-1) {
            c++;
        }
        else {
            if(b==v.size()-2){
                a++;
                b=a+1;
                c=b+1;
            }
            else{
                b++;
                c=b+1;
            }
        }
    }
    cout << ans;
}