백준 14502 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

- N과 M이 최대 2^3이므로, 많은 for문을 중첩시킬 수 있다. (NM <= 2^6 = 64이므로 O(NM^4)까지도 가능하다.) 

 

- 백트래킹을 통해 벽을 놓을 수 있는 모든 경우의 수를 고려한다. 백트래킹은 DFS로 구현한다.

 

- 바이러스의 전파는 BFS 기법을 활용하고, 완료 된 후 배열을 순회하면서 안전구역을 체크하여 answer를 최신화한다.

 

- 백트래킹과 DFS/BFS를 섞은 문제이며, 난이도 자체는 높지 않다고 생각. 그런데 구현 시간이 조금 오래 걸린다.

 

#include <iostream>
#include <queue>
#include <algorithm>

int lab[8][8]; // 연구소 상황
int temp[8][8]; // 벽 3개를 세웠을 때의 연구소
int answer, n, m;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
using namespace std;
#define TEMP_WALL 3

void bfs() {
	bool visited[8][8]; // 해당 구역 방문 여부 체크
	int virus[8][8]; // 바이러스 전파 후 정보 
	for (int i = 0; i < n; i++) { // temp의 정보를 먼저 담는다.
		for (int j = 0; j < m; j++) {
			virus[i][j] = temp[i][j];
		}
	}
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (virus[i][j] == 2) q.push({ i,j });
		}
	}
    // bfs 진행
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (virus[nx][ny] == 0) {
				virus[nx][ny] = 2;
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
    // 안전구역 검사 후, answer 최신화
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (virus[i][j] == 0) cnt++;
		}
	}
	answer = max(answer, cnt);
}

void wall(int num_of_wall) {
	if (num_of_wall == TEMP_WALL) { // 세운 벽이 3개라면, bfs를 통해 안전구역 조사
		bfs();
		return;
	}
    // 백트래킹으로 벽을 놓을 수 있는 모든 경우의 수 조사
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (temp[i][j] == 0) {
				temp[i][j] = 1;
				wall(num_of_wall + 1);
				temp[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lab[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lab[i][j] == 0) { // 처음 세울 벽을 잡고, temp에 복사한다.
				for (int k = 0; k < n; k++) {
					for (int l = 0; l < m; l++) {
						temp[k][l] = lab[k][l];
					}
				}
                // 처음 벽을 세우고, 백트래킹 함수 wall 호출
				temp[i][j] = 1;
				wall(1);
				temp[i][j] = 0;
			}
		}
	}
	cout << answer;
	return 0;
}