백준 14502번 연구소 (BFS)

 

이번에는 BFS를 이용한 문제를 풀어보자.

이 문제는Brute-Force 방법으로도 풀 수 있는 문제이다.

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

14502번: 연구소

---

값이 0에 해당하는 위치가 빈 칸(clean한 상태)며, 이를 모두 순회하면서 1(벽을 세움)을 3개 대입하면서 바이러스가 퍼지는 것을 BFS로 측정한다.

이를 구현하기 위해 3중 for문을 이용해서 구현하였으며 bfs를 호출하고 0 값을 카운트하는 함수를 호출하여 가장 많은 값을 출력하도록 했다.

계산을 여러번 해야하므로 tempMap을 이용하여 input 값을 계속해서 복사하는 방식을 이용했다.

3중 for문을 통해 brute-force를 구현하는 것 외에는 일반적인 BFS문제이다.

 

<소스코드>

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

using namespace std;

int map[8][8];
int tempMap[8][8];
int visited[8][8];

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

queue<pair<int, int>> q;
queue<pair<int, int>> temp_q;

void bfs() {
	memset(visited, 0, sizeof(visited));

	while (!temp_q.empty()) {
		int cx = temp_q.front().first;
		int cy = temp_q.front().second;
		temp_q.pop();
		visited[cx][cy] = 1;

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

			if (visited[nx][ny] == 0 && tempMap[nx][ny] == 0) {
				temp_q.push(make_pair(nx, ny));
				visited[nx][ny] = 1;
				tempMap[nx][ny] = 2;
			}
		}
	}
}

int cntZero() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (tempMap[i][j] == 0) {
				cnt++;
			}
		}
	}

	return cnt;
}

void copyMap() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tempMap[i][j] = map[i][j];
		}
	}
}

int main(void) {	
	cin >> n >> m;

	vector<pair<int, int>> clean_q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			
			if (map[i][j] == 0) {
				clean_q.push_back(make_pair(i, j));
			}
			if (map[i][j] == 2) {
				q.push(make_pair(i, j));
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < clean_q.size() - 2; i++) {
		for (int j = i+1; j < clean_q.size() - 1; j++) {
			for (int k = j+1; k < clean_q.size(); k++) {
				copyMap();
				temp_q = q;
				
				tempMap[clean_q[i].first][clean_q[i].second] = 1;
				tempMap[clean_q[j].first][clean_q[j].second] = 1;
				tempMap[clean_q[k].first][clean_q[k].second] = 1;

				bfs();

				ans = max(ans, cntZero());

			}
		}
	}

	cout << ans << "\n";
	
	return 0;
}