[백준] 14502번 - 연구소 (골드 5)

문제

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

14502번: 연구소

 

---

 

접근 방식

• 지도 공간 중의 0인 위치를 찾아, 중복 되지 않고 3개의 위치를 선택한다. (순열)
• 해당 위치에 벽을 세우고 BFS로 바이러스를 확산시킨다. (4 방향)
• 모든 지도에 수행하면서 안전한 영역(0인 곳)이 가장 많이 남은 개수를 찾는다.

---

 

코드

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

using namespace std;

void func_14502_virusInfect(int n, int m, int **_map, queue<pair<int, int>> q) {
	pair<int, int> cur;
	int _x, _y;
	int direc[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

	while (!q.empty()) {
		cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			_x = cur.first + direc[i][0];
			_y = cur.second + direc[i][1];

			if (_x >= n || _x < 0)
				continue;
            
			if (_y >= m || _y < 0)
				continue;

			if (_map[_x][_y] == 1 || _map[_x][_y] == 2) {
				continue;
			}

			_map[_x][_y] = 2;
			q.push({_x, _y});
		}
	}
}

int main() {
	int n, m, cnt, max_safeZone = 0;

	vector<pair<int, int>> _map_v;
	queue<pair<int, int>> q;

	cin >> n >> m;
	
	int** _map = new int* [n];
	int** _map_copy = new int* [n];

	for (int i = 0; i < n; i++) {
		_map[i] = new int[m];
		_map_copy[i] = new int[m];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> _map[i][j];

			if (_map[i][j] == 0) {
				_map_v.push_back({i, j});
			}
		}
	}

	sort(_map_v.begin(), _map_v.end());

	do {
		while (!q.empty()) {
			q.pop();
		}

		for (int i = 0; i < n; i++) {
			memcpy(_map_copy[i], _map[i], sizeof(int) * m);
		}
        
		for (int i = 0; i < 3; i++) {
			_map_copy[_map_v.at(i).first][_map_v.at(i).second] = 1;
		}
        
	    for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (_map_copy[i][j] == 2) {
					q.push({ i, j });
				}
			}
		}

		func_14502_virusInfect(n, m, _map_copy, q);

		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (_map_copy[i][j] == 0) {
					cnt++;
				}
			}
		}
		
		if (cnt > max_safeZone) {
			max_safeZone = cnt;
		}

		reverse(_map_v.begin() + 3, _map_v.end());
	} while (next_permutation(_map_v.begin(), _map_v.end()));

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

---

 

결과