[BFS & 완전탐색] 백준 14502 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

수행 시간 : 1시간 40분

 

삼성SW 역량테스트 기출문제. 난이도는 골드5. 이 알고리즘 문제에서 가장 힘들었던 부분은 벽이 3개 세워지면 벽을 초기화 시키화 시키는 부분 이였다. 그것도 벽을 다 초기화 시키는 것이 아닌 마지막 벽만 완전탐색으로 map 끝까지 돌려주면서 바이러스의 최소값을 찾아줘야 한다.

void make_wall(int x, int y) { //브루트포스로 1을 세워본다.
	for (int i = x; i < n;i++) {
		for (int j = y;j < m;j++) {
			if (map[i][j] == 0) {
				wall_cnt++;
				if (wall_cnt == 3) {
					memset(visited, 0, sizeof(visited));
					map[i][j] = 1;
					memcpy(copy_map, map, sizeof(map));
					for (int k = 0;k < virus_cnt;k++) {
						spread(virus_x[k], virus_y[k]);
					}
					cal();
					map[i][j] = 0;
					wall_cnt--;
				}
				else {
					map[i][j] = 1;
					make_wall(i, j + 1);
					wall_cnt--;
					map[i][j] = 0;
				}
			}
		}
		y = 0;
	}
}

이렇게 재귀를 통해 벽 1,2를 놔둔 상태로 3을 전체로 돌려주고, 벽 1을 놔둔 상태로 2, 3을 전체로 돌려주고 이런식으로 구현하다 보니 생각보다 코드짜기가 힘들었다.

 

++전체코드

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

int map[9][9];
int copy_map[9][9];
bool visited[9][9];
int virus_x[11];
int virus_y[11];
int n, m, virus_cnt;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int max_cnt = 0;
int wall_cnt = 0;

void spread(int a, int b) { //바이러스 확산 시킴
	if (visited[a][b]) {
		return;
	}
	visited[a][b] = true;
	int spread_cnt = 0;
	queue<pair<pair< int, int>, int >> q;
	q.push({ { a,b }, 0 });
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		spread_cnt = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			if (nx < n && nx >= 0 && ny < m && ny >= 0) { //맵안에잇어야됌
				if (visited[nx][ny] == false && copy_map[nx][ny] == 0) { //visited가 false + map이 안전지대이면
					visited[nx][ny] = true;
					copy_map[nx][ny] = 2;
					q.push({ { nx,ny }, spread_cnt + 1 });
				}
			}
		}
	}
}
void cal() {
	int cnt = 0;
	for (int i = 0; i < n;i++) {
		for (int j = 0; j < m;j++) {
			if (copy_map[i][j] == 0) {
				cnt++;
			}
		}
	}
	if (max_cnt < cnt) {
		max_cnt = cnt;
	}
}
void make_wall(int x, int y) { //브루트포스로 1을 세워본다.
	for (int i = x; i < n;i++) {
		for (int j = y;j < m;j++) {
			if (map[i][j] == 0) {
				wall_cnt++;
				if (wall_cnt == 3) {
					memset(visited, 0, sizeof(visited));
					map[i][j] = 1;
					memcpy(copy_map, map, sizeof(map));
					for (int k = 0;k < virus_cnt;k++) {
						spread(virus_x[k], virus_y[k]);
					}
					cal();
					map[i][j] = 0;
					wall_cnt--;
				}
				else {
					map[i][j] = 1;
					make_wall(i, j + 1);
					wall_cnt--;
					map[i][j] = 0;
				}
			}
		}
		y = 0;
	}
}

int main() {
	cin >> n >> m;
	virus_cnt = 0;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				virus_x[virus_cnt] = i;
				virus_y[virus_cnt] = j;
				virus_cnt++;
			}
		}
	}
	make_wall(0, 0);
	cout << max_cnt;
}