[C++] 백준 14502 연구소

문제 링크

---

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

14502번: 연구소

접근 방법

---

 위 문제는 벽 3개를 세울 수 있는 모든 경우에 대해 벽을 세운 후 바이러스를 퍼뜨려 안전영역의 최댓값을 구하면 된다. 

 

 벽을 3개를 세우는 방법은 백트래킹으로 가능하나 for문을 3중으로 사용하는 것도 가능하다. 필자는 3중 for문을 사용했으며, 취향에 따라 방법을 달리하여도 된다. 벽을 3개를 세운 뒤 바이러스를 퍼뜨리는 방법은 BFS를 사용하면 된다.

 

1. 일단 main()에서 입력을 받는 동시에 빈 공간의 위치와 바이러스의 위치의 정보를 저장해 두었다.

for (int i = 0; i < n; i++) 
	for (int j = 0; j < m; j++) {
    cin >> room[i][j];
    	if (room[i][j] == 0)
    		zeros.push_back({ i,j }); //빈공간
    	else if (room[i][j] == 2)
    		virus.push_back({ i,j }); //바이러스 초기위치
    }

2. 3중 for문을 사용하여 벽 3개를 세울 위치를 각각 first, second, third로 받았으며 해당 위치를 map에서 1로 변경 후 bfs를 사용하여 바이러스를 퍼뜨려 바이러스가 퍼진 공간을 cnt로 반환받았으며 안전영역의 수는 아래와 같이 구할 수 있다.

int safe = zeros.size() - 3 - cnt;

safe(바이러스가 퍼진 후 안전영역) =

zeros.size()(바이러스가 퍼지기 이전의 안전영역 수) - 3(벽을 새로 세운 공간) - cnt(바이러스가 퍼진 영역)

 

 

 

소스 코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;

int room[8][8];
vector <pair<int, int>> zeros;
vector <pair<int, int>> virus;
pair<int, int> direction[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int n, m;
int max_ = 0;

int bfs(int x, int y) {

	int cnt = 0;
	queue < pair<int, int>> q;
	q.push({ x,y });
	while (!q.empty()) {
		auto elem = q.front();
		int i = elem.first;
		int j = elem.second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int next_x = i + direction[k].first;
			int next_y = j + direction[k].second;
			if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m && room[next_x][next_y] == 0) {
				q.push({ next_x, next_y });
				room[next_x][next_y] = 2;
				cnt++;
			}
		}
	}
	return cnt;
}

void build_wall(int n, int m) {

	for (int i = 0; i < zeros.size(); i++) {
		for (int j = i + 1; j < zeros.size(); j++) {
			for (int k = j + 1; k < zeros.size(); k++) {
				int cnt = 0;
				auto first = zeros[i];
				auto second = zeros[j];
				auto third = zeros[k];
				room[first.first][first.second] = 1;
				room[second.first][second.second] = 1;
				room[third.first][third.second] = 1;
				for (auto &elem : virus) {
					cnt += bfs(elem.first, elem.second); //바이러스가 퍼진 영역의 수
				}
				int safe = zeros.size() - 3 - cnt;
				max_ = max(max_, safe);
				for (auto &elem : zeros) {
					room[elem.first][elem.second] = 0;
				}
				room[first.first][first.second] = 0;
				room[second.first][second.second] = 0;
				room[third.first][third.second] = 0;
			}
		}
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(room, -1, sizeof(room));

	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) {
			cin >> room[i][j];
			if (room[i][j] == 0)
				zeros.push_back({ i,j }); //빈공간
			else if (room[i][j] == 2)
				virus.push_back({ i,j }); //바이러스 초기위치
		}
	build_wall(n, m);
	cout << max_ << "\n";
}

개발 환경 : VS 2019

질문, 지적 환영입니다.