백준 17142 c++ : 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

고생한 포인트

 

1. 모두 활성화 시키는게 아니라 모두 바이러스로 채워야한다는 포인트를 제대로 못봤다!!

-> 무슨 뜻이냐, 2는 남아있어도 되고 0만 없으면 된다!!

 

-> 요런 경우 

 

 

 

2. 시간초과로 고생했다.

-> while문으로 BFS 레벨 한번마다 0이 남아있나 없나 여부를 확인했더니 시간초과가 떠버리더라

-> 0찾는거를 그냥 while문 밖으로 뺴면 while 문안에서 1과 2만 남는 경우를 캐치를 못하더라

 

3. (2) 즉 활성화되지 않은 바이러스를 처리하는게 힘들었다.

-> 이번턴에 하나라도 빈칸을 바이러스로 채웠으면 나머지랑 상관없이 한턴을 소비 (flag 처리)

-> 만약 2(활성화 되지 않은 바이러스)를 만나면 이놈을 거쳐야지 채울 수 있는 빈칸이 있나 여부를 확인 후 flag 처리

 

요 테스트 케이스같은 경우!!

 

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 0 2 0
1 1 1 1 1

 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int n,m;
int map[51][51];
int back_up[51][51];
int visited[51][51];
vector<pair<int, int> > choosed; // 바이러스가 시작할 위치!
vector<pair<int, int> > possible_place;
int visited_virus[3000];
int answer = 987654321;

int d_r[4] = { 1,-1,0,0 };
int d_c[4] = { 0,0,1,-1 };

void gogo()
{
	queue<pair<int, int> >q;
	for (int i = 0; i < choosed.size(); i++)
	{
		q.push(choosed[i]);
		visited[choosed[i].first][choosed[i].second] = 1;
		map[choosed[i].first][choosed[i].second] = 1;//바이러스 처리
	}

	int result = 0;
	while (!q.empty())
	{
		int flag = 0;
		int s = q.size();
		for (int k = 0; k < s; k++)
		{
			int r = q.front().first;
			int c = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				int new_r = r + d_r[i];
				int new_c = c + d_c[i];

				if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)//지도 밖
					continue;
				if (visited[new_r][new_c] == 1)//방문했었음
					continue;
				if (map[new_r][new_c] == 1)//벽이거나 그냥 바이러스
					continue;
				if (map[new_r][new_c] == 0)
				{
					flag = 1;
				}
				if (map[new_r][new_c] == 2)//이놈이 바이러스야 근데 여기서 끝나는게 아니라 얘가 감염시킬 놈이 있어!
				{
					for (int a = 0; a < 4; a++)
					{
						if (new_r + d_r[a] < 0 || new_c + d_c[a] < 0 || new_r + d_r[a] >= n || new_c + d_c[a] >= n)
							continue;
						if (map[new_r + d_r[a]][new_c + d_c[a]] == 0)
							flag = 1;
					}
				}
				visited[new_r][new_c] = 1;
				map[new_r][new_c] = 1;
				q.push(make_pair(new_r, new_c));
			}
		}
		if (flag == 0)
			break;
		result++;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == 0)//하나라도 감염 안된 캄 있으면!!
				return;
		}
	answer = min(answer, result);
}


void choose(int index, int total)
{
	if (choosed.size() == total)
	{
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				map[i][j] = back_up[i][j];

		gogo();
		return;
	}

	for (int i = index; i < possible_place.size(); i++)
	{
		if (visited_virus[i] == 0)
		{
			visited_virus[i] = 1;
			choosed.push_back(possible_place[i]);
			choose(i, total);
			visited_virus[i] = 0;
			choosed.pop_back();
		}

	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			back_up[i][j] = map[i][j];
			if (map[i][j] == 2)
				possible_place.push_back(make_pair(i, j));
		}
	choose(0, m);
	
	if (answer == 987654321)
		answer = -1;
	cout << answer << endl;
	return 0;
}