백준 14502번 연구소 (삼성 SW 역량테스트 기출문제)

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

사용한 알고리즘: DFS, Brute Force(완전 탐색)

문제에서는 최대 8x8 그래프를 주고, 이후 각각의 지점에서 바이러스(2), 벽(1), 빈 영역(0) 에 대한 정보를 주고 있습니다.
이때 벽 (무조건)3개를 빈 영역(0)에 세워서 바이러스를 격리시켜(벽으로 막아) 바이러스가 퍼지지 않는 안전 영역을 만들고, 이렇게 만들 수 있는 최대 안전 영역의 크기를 구하라고 하고 있습니다.

기본적인 제 풀이 생각은 다음과 같습니다.
 우선 전체 영역에서 벽만을 제외한 영역의 크기를 Area 라고 했을 때 (바이러스가 있는 영역을 포함한 크기), 주어지는 그래프의 크기가 최대 8x8로 매우 작게 주어지므로,
벽 3개를 세우는 모든 경우를 다 따져보고 (Brute Force), 각 경우마다 안전 영역을 구하여,
최대 안전 영역의 값을 각 경우마다 최신화 해 주는 것입니다.
 이때 virus가 있는 영역에서부터 DFS를 사용하여 virus가 퍼질 수 있는 영역의 크기를 계산해주고 이를 Area에서 빼주는 식으로 안전영역의 크기를 계산했습니다.

저의 풀이 과정을 써보면 다음과 같습니다.

(1) 입력을 받으면서 (virus영역포함, 벽만을 제외) Area 를 계산해 주고, 벽을 세울 수 있는 빈 영역(0)을 입력 받으면, 해당 위치를 pair형태로 Wall이라는 이름의 vector안에 저장해 줍니다. 또한 virus가 있는 영역의 위치를 pair형태로 Virus라는 이름의 vector안에 저장해 주었습니다.

(2) 과정(1)에서 모아놓은 vector (Wall) 을 살펴보며 벽 3개를 추가로 세울 수 있는 모든 경우의 수를 따져봅니다. 이때 3중 for 구문을 사용하였는데, 중복을 최소화 해주기 위해 범위 설정을 다음과 같이 해주었습니다.
 처음 설치할 벽(첫번째 for구문: i)는 0 ~ Wall.size - 2 ( 첫번째 벽을 설치한 뒤, 벽 2개를 추가로 설치해야 하니 설치할 수 있는 영역을 적어도 2개는 남겨두어야 한다고 생각했습니다.)
 두번째 설치할 벽(두번째 for구문: j)는 i+1 ~ Wall.size - 1 (마찬가지로 두번째 벽을 설치한 뒤, 벽 1개를 추가로 설치해야 하니 설치할 수 있는 영역을 적어도 1개는 남겨두어야 한다고 생각했습니다.)
 세번째 설치할 벽(세번째 for구문: k)는 j+1 ~ Wall.size
로 설정해주었습니다.

(3) 벽을 설치한 후 안전영역의 크기를 계산해주었습니다. virus가 있는 영역에서 부터 virus가 퍼질 수 있는 모든 영역의 크기를 DFS로 찾아주어, 이를 Area에서 빼주는 식으로 안전영역의 크기를 구했습니다.


 문제를 푸는 알고리즘은 특별할 건 없었지만, 저에게 있어 구현이 조금 힘든 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	int N, M, Area, ans, arr[8][8];
	int dx[4] = {1,-1,0,0};
	int dy[4] = {0,0,1,-1};
	vector<pii> Wall;
	vector<pii> Virus;
	bool visited[8][8];
	// 못쓰는 area 계산
	int UnSafeArea(pii a, pii b, pii c, int x, int y){
	visited[x][y] = true;
	int temp = 1;
	for (int i = 0; i < 4; ++i){
	int nx = x+dx[i];
	int ny = y+dy[i];
	if(nx<0||nx>=N||ny<0||ny>=M) continue;
	if(nx==a.first&&ny==a.second) continue;
	if(nx==b.first&&ny==b.second) continue;
	if(nx==c.first&&ny==c.second) continue;
	if(visited[nx][ny] || arr[nx][ny]==1) continue;
	temp+=UnSafeArea(a,b,c,nx,ny);
	}
	return temp;
	}
	int UA(pii A, pii B, pii C){
	int cor = 0;
	memset(visited,false,sizeof(visited));
	for (int i = 0; i < Virus.size(); ++i){
	int X = Virus[i].first;
	int Y = Virus[i].second;
	if(!visited[X][Y]) cor+=UnSafeArea(A,B,C,X,Y);
	}
	return cor;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < M; ++j){
	cin >> arr[i][j];
	if(arr[i][j]==0){
	Area++;
	Wall.push_back(pii(i,j));
	}
	else if(arr[i][j]==2) Virus.push_back(pii(i,j));
	}
	}
	Area-=3;
	Area+=Virus.size();
	for (int i = 0; i < Wall.size()-2; ++i){
	for (int j = i+1; j < Wall.size()-1; ++j){
	for (int k = j+1; k < Wall.size(); ++k){
	ans = max(ans, Area-UA(Wall[i],Wall[j],Wall[k]));
	}
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 14502.cpp hosted with ❤ by GitHub