[삼성코테기출문제] 연구소

연구소

문제

어려웠다… 풀고나서 생각해보니 BFS, DFS, 브루트포스 모두 섞인 문제였다.. 처음에 벽 3개를 세울 수 있는 모든 경우를 생각해야하나? 다른 방법은 없나..? 모든 경우를 생각하면 시간초과가 나오지 않을까? 라는 걱정이 먼저 앞섰지만, 최대 범위가 8 x 8 밖에 안되서 괜한 걱정이었다. 그리고 이 문제를 통해 조합을 구현하는 방법을 확실히 알게된 것 같다.

문제 풀이

입출력 조건

N x N에서 3개를 골라 벽을 세우는 모든 경우를 생각해야하므로 그 경우를 DFS를 통한 Brute Force를 하고 벽 세 개 놓을 곳을 선택한 후에는 BFS를 통하여 바이러스를 확산 시켜 주었다.

풀이 과정

1. 먼저 (N x M)을 안전구역이라고 생각하고 벽과 바이러스를 빼서 최초 안전구역을 구해주고, 바이러스의 좌표는 따로 담아둔다.
2. 모든 경우를 탐색할 것 이므로 (0,0) ~(M-1,N-1) 의 한 칸 한 칸에 대하여 빈 공간이면 Tmp[][]배열에 맵을 복사해준다. 그리고 해당 좌표에 벽을세우고 안전구역의 수 하나를 감소시킨다. 벽을 하나 세웠으므로 makeWall()함수 매개변수에 1을 넣고 재귀함수로 넘어간다. 이 부분이 _조합 _을 구현한 부분이다.
3. 재귀함수 안에서도 역시 빈공간을 찾아 벽을 세우고 새로 세운 벽의 수를 카운트 한다. 만약 벽의 수가 3이라면 BFS()로 넘어간다.
4. 이 때 안전구역 역시 BFS 후 다시 이전으로 돌아와야하므로 현재 안전구역을 z=Safe해주어 z를 이용하여 안전구역을 카운트하고, 바이러스 확산 역시 매번 다시 생각해야하므로 맵을 복사하여 탐색해준다.
5. 바이러스가 확산될 수 있는 구역이라면 해당 구역을 바이러스로 바꿔주고 방문체크를 한다. 그리고 안전구역 z를 감소시켜 준다.
6. 바이러스 확산이 끝났으면 안전구역의 값이 최대인지 판별하여 처리하여준다.
7. 위 과정을 반복하여 안전구역의 최대치를 찾아준다.

#include <iostream>

using namespace std;
const int MAX = 8;

int N, M;
int Map[MAX][MAX];
int Tmp[MAX][MAX];
int Visit[MAX][MAX];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,-1,1 };

int Max;
int Safe;
typedef struct Pos {
	int x, y;
};
Pos Virus[10]; int v_Idx;

Pos Q[MAX*MAX]; int f, r;
void push(int x, int y) { Q[r++] = { x,y }; }
Pos pop() { return Q[f++]; }

void Input() {
	cin >> N >> M;
	Safe = M * N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
			if (Map[i][j] != 0) {
				Safe--;
				if (Map[i][j] == 2)	Virus[v_Idx++] = { j,i };
			}
		}
	}
}
void Bfs() {
	int z = Safe;
	int next[MAX][MAX];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			next[i][j] = Tmp[i][j];
			Visit[i][j] = false;
		}
	f = r = 0;
	for (int k = 0; k < v_Idx; k++) {
		push(Virus[k].x, Virus[k].y);
		Visit[Virus[k].y][Virus[k].x] = true;
	}
	
	while (f != r) {
		Pos cur = pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < M&&ny < N&&next[ny][nx]==0) {
				if (!Visit[ny][nx]) {
					next[ny][nx] = 2;
					Visit[ny][nx] = true;
					z--;
					push(nx, ny);
				}
			}
		}
	}
	if (Max < z)Max = z;
}
void makeWall(int cnt){
	if (cnt == 3)	{
		Bfs();
		return;
	}
	for (int i = 0; i < N; i++)	{
		for (int j = 0; j <M; j++){
			if (Tmp[i][j] == 0){
				Tmp[i][j] = 1;
				Safe--;
				makeWall(cnt + 1);
				Tmp[i][j] = 0;
				Safe++;
			}
		}
	}
}
void Solution() {
	Input();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 0) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						Tmp[i][j] = Map[i][j];
					}
				}
				Tmp[i][j] = 1;
				Safe--;
				makeWall(1);
				Tmp[i][j] = 0;
				Safe++;
			}
		}
	}
	cout << Max << endl;
}
int main() {
	freopen("08.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	Solution();
	return 0;
}