5) 백준 14502 - 연구소

<문제>

www.acmicpc.net/problem/14502

14502번: 연구소

솔직히 감이 처음에는 안 잡혔지만 결론은 노가다 였다.

 

<코드>

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

using namespace std;

queue<pair<int, int> > q;
vector<pair<int, int> > v;

int map[8][8] = {0, };
int cpy_map[8][8];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool check[8][8] = {0, };

int N, M;
int answer = 0;
int blank = -3;

int bfs() {
	bool check_2[8][8] = {0, };
	int n_blank = blank;
	for(int i = 0; i < v.size(); i++) {
		q.push(make_pair(v[i].first, v[i].second));
	}
	
	while(!q.empty()) {
		int size = q.size();
		for(int i = 0; i < size; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for(int j = 0; j < 4; j++) {
				if(map[x + dx[j]][y + dy[j]] == 0 
				&& (x + dx[j]) < N && (y + dy[j]) < M 
				&& !check_2[x + dx[j]][y + dy[j]] 
				&& (x + dx[j]) >= 0 && (y + dy[j]) >= 0) {
					q.push(make_pair(x + dx[j], y + dy[j]));
					check_2[x + dx[j]][y + dy[j]] = 1;
					map[x + dx[j]][y + dy[j]] = 2;
					
					n_blank--;
				}
			}
		}
	}
	return n_blank;
}

void make_wall(int cnt) {
	if(cnt == 3) {
		memcpy(cpy_map, map, sizeof(map));
		int Max = bfs();
		memcpy(map, cpy_map, sizeof(cpy_map));
		answer = max(Max, answer);
		return;
	}
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if(map[i][j] == 0 && !check[i][j]) {
				map[i][j] = 1;
				check[i][j] = 1;
				make_wall(cnt+1);
				map[i][j] = 0;
				check[i][j] = 0;
			}
		}
	}
}

int main(void) {
    ios::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 >> map[i][j];
			if(map[i][j] == 0) blank++;
			if(map[i][j] == 2) {
				v.push_back(make_pair(i, j));
			}
		}
	}
	
	make_wall(0);
	
	cout << answer << endl;
	
}

정신없는 코드.

일단 풀기 전에 기본적인 세팅을 해야 한다.

 

1. queue를 사용하고 나면, 다시 원래 queue로 돌려보내야 하지만, 큐는 복사하지 못하므로(내가 모르는 것일 수도..ㅠ) 본인은 큐에 들어간 모든 값들을 벡터에 저장했다.

2. 원래의 map으로 돌려보내기 위한 map의 복사본이 필요하다. 이를 cpy_map으로 정했다. 이는 bfs에 들어가기 전과 후에 원래 모습으로 돌려보내 주기 위한 용도로 쓸 것이다.

3. 감염되기 전의 빈칸 개수(blank)를 저장해둔다. 감염이 될 때마다 빈칸 개수를 줄여갈 것(n_blank를 사용)이다.

 

방법은 다음과 같다.

 

원래의 맵에서 벽을 3개 무조건 세워야 한다. 처음에 노가다 생각할 수 있는데 맞다. 노가다가.

임의로 (중복 안되게) 빈칸을 3개 골라서 벽을 세운다. 그 후 이 map을 활용해서 bfs를 돌린다. bfs가 끝나면 bfs 하기 전으로 돌려놓는다. 반복한다.

 

본인 생각에는 브루트 포스와 BFS가 섞여있는 듯하다. 어려웠다..ㅠㅠㅠ

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

때로는 무식한 게 답인 듯....ㅎㅎㅎㅎㅎㅎㅎㅎㅎ

기 분 조 아 !