[BOJ] 백준 14502 연구소 c++

BOJ 문제 링크: https://www.acmicpc.net/problem/14502

14502번: 연구소

연구소가 N*M크기 행렬로 주어진다. 연구소 각 칸의상태는 빈칸(0), 벽(1), 바이러스(2) 세가지 중 하나이다.

바이러스가 아직 퍼지지 않은 상태지만, 바이러스가 벽에 막히지 않는다면 상하좌우로 인접한 빈 칸에 퍼져 나갈 예정이다.

벽을 꼭 3개 세워서 바이러스가 퍼져나가는것을 막는다 했을때, 빈칸으로 남을 수 있는 안전영역 크기의 최댓값을 구하는 문제이다.

 

3개의 벽을 세우는 모든 경우를 구하고, 각 경우마다 바이러스가 퍼졌을때 0으로 남아있는 칸의 갯수를 구하는 식으로 문제를 풀 수있다.

벽을 세울때는 N*M개의 각 칸들을 일차원으로 풀어서 here로 표현한다.

현재영역(here)이 0이면 here에 벽을 설치하거나, 설치안하거나 두가지 경우를 계산하고 here이 0이 아니면 바로 다음칸(here+1)로 넘어간다.

안전영역의 넓이를 구할때는 bfs를 이용하는데 연구소상태(lab)를 훼손시키면 안되므로

visited라는 이차원 배열을 따로 두어서 바이러스가 이미 퍼진곳인지, 아직 퍼지지 않은 곳인지 표현한다.

 

 

	#include<iostream>
	#include<queue>
	#include<cstring>
	using namespace std;
	int n, m;
	// 연구소 상태
	int lab[8][8];
	// 바이러스 퍼짐 여부
	bool visited[8][8];
	// 연구소에 있는 벽의 총 갯수
	int walls;
	// 안전영역 최대크기
	int result;
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { -1, 1, 0, 0 };
	// 바이러스가 퍼졌을때 연구소에 있는 2의 갯수 구하기
	int fillVirus(queue<pair<int, int>>& virusPos, int virus) {
	while (!virusPos.empty()) {
	int x = virusPos.front().first;
	int y = virusPos.front().second;
	virusPos.pop();
	for (int i = 0; i < 4; i++) {
	int nextX = x + dx[i];
	int nextY = y + dy[i];
	// 연구소를 벗어나면 continue
	if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n)continue;
	// 방문하고자 하는 곳이 0이고 아직 바이러스가 안퍼진 곳이면
	if (lab[nextY][nextX] == 0 && visited[nextY][nextX] == 0) {
	// 해당장소 queue에 넣고 visited체크, virus갯수 증가
	virusPos.push(make_pair(nextX, nextY));
	visited[nextY][nextX] = true;
	virus++;
	}
	}
	}
	return virus;
	}
	// 안전 영역 넓이 구하기
	void calcArea() {
	queue<pair<int, int>> virusPos;
	int virus = 0;
	memset(visited, 0, sizeof(visited));
	// bfs를 위해 바이러스가 있는곳 queue에 넣기
	// visited, virus 계산
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
	if (lab[i][j] == 2) {
	virusPos.push(make_pair(j, i));
	visited[i][j] = true;
	virus++;
	}
	// 안전영역 = 전체넓이 - (벽의 총 갯수 + virus의 갯수)
	int ret = n * m - (walls + fillVirus(virusPos, virus));
	result = max(result, ret);
	}
	// 벽 설치
	void constructWall(int wall, int here) {
	// 벽 설치 다했으면 안전영역 계산
	if (wall == 0) {
	calcArea();
	return;
	}
	int area = n * m;
	// 더 이상 벽을 설치할 곳이 없는 경우 return
	if (here >= area) return;
	int x = here % m;
	int y = here / m;
	// 현재 영역이 0이면 벽을 설치 하는 경우
	if (lab[y][x] == 0) {
	// 벽 설치하고 다음 영역으로 넘어감
	lab[y][x] = 1; walls++;
	constructWall(wall - 1, here + 1);
	// 원상복구
	lab[y][x] = 0; walls--;
	}
	// 현재 영역은 벽을 설치 안하고 다음 영역으로 넘어가는 경우
	constructWall(wall, here + 1);
	}
	int main() {
	cin >> n >> m;
	walls = result = 0;
	for(int i = 0; i < n; i++)
	for (int j = 0; j < m; j++) {
	cin >> lab[i][j];
	if (lab[i][j] == 1)
	walls++;
	}
	constructWall(3, 0);
	cout << result << endl;
	}

view raw [BOJ] 백준 14502 연구소.cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314502.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!