Baekjoon17142-연구소3

백준 사이트 17142 - 연구소3 문제입니다.

1. 문제

https://www.acmicpc.net/problem/17142

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
질문글을 보다보니 삼성기출문제로 나왔던 문제인 것 같습니다.
백준에서는 Gold4의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 전체적으로 신경쓸 게 많은 문제였습니다.
• 가장 먼저 0.25초 제한으로 바이러스를 M개 고를 떄 고른 바이러스 바로 다음을 탐색하기 위해 코드를 작성해야 했습니다.
• BFS를 돌고 맵을 탐색하기 보다는 빈공간을 먼저 세주고 빈공간이 다 채워졌을 때 결과를 도출하도록 코드를 짰습니다.
• 처음에는 result(최소 시간 값을) 300정도로 줬는데 70%에서 계속 틀려서 987654321값을 주니 통과했습니다. 이것 때문에 애 많이 먹었습니다.

---

5. code

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

const int MAX = 51;

int MAP[MAX][MAX] = { 0, };
int temp[MAX][MAX];
bool v[MAX][MAX] = { false, };
queue<pair<pair<int, int>, int>> q;
int arrx[11] = { 0, };
int arry[11] = { 0, };

int N, M;
int counting = 0;
int result = 987654321;

//좌표이동
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

void Input() {
	cin >> N >> M;
	int temp = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j) {
			cin >> temp;
			if (temp == 0)
				++counting;
			MAP[i][j] = temp;
		}
	}

}
void BFS()
{
	memcpy(temp, MAP, sizeof(MAP));
	memset(v, false, sizeof(v));
	int tempresult = 0;
	int tempcounting = counting;
	for (int i = 0; i < M; ++i)
	{
		//cout << arrx[i] << arry[i] << "\n";
		q.push(make_pair(make_pair(arrx[i], arry[i]), 0));
		v[arrx[i]][arry[i]] = true;
	}

	while (!q.empty())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		int minu = q.front().second;
		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];
			if (0 <= newX && newX < N && 0 <= newY && newY < N && v[newX][newY] == false && temp[newX][newY] != 1)
			{
				if (temp[newX][newY] == 0)
				{
					--tempcounting;
					if (tempcounting == 0)
					{
						result = min(result, minu + 1);
					}
				}
				temp[newX][newY] = 2;
				q.push(make_pair(make_pair(newX, newY), minu + 1));
				v[newX][newY] = true;
			}
		}
	}
}

void virus(int x, int y, int cnt) {
	if (cnt == M) {
		BFS();
		return;
	}
	bool check = false;
	for (int i = x; i < N; ++i)
	{
		int j;
		if (check == false)
		{
			j = y;
			check = true;
		}
		else
			j = 0;
		for (; j < N; ++j)
		{
			if (MAP[i][j] == 2)
			{
				MAP[i][j] = 3;
				arrx[cnt] = i;
				arry[cnt] = j;
				virus(i, j, cnt + 1);
				MAP[i][j] = 2;
			}
		}
	}
}

void Solve() {
	//바이러스 선별 먼저
	//virus
	//복사 해두기
	if (counting == 0)
		cout << 0 << '\n';
	else
	{
		virus(0, 0, 0);
		if (result == 987654321)
			result = -1;
		cout << result;
	}
}

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

	Input();
	Solve();


}

---

6. 후기

사실 반쯤 포기하고 다른 사람들꺼 코드 보면서 고쳤는데, 그 로직만 바꾼 그 코드들도 70%에서 오류가 나길래 이건 나의 로직 문제가 아니고 값이 뭔가 잘 못된 것을 인지해서 result값 바꾸니까 바로 성공..