[백준] 14502번 연구소 (C++, JAVA)

14502번: 연구소

BFS, 완전 탐색 문제이다.

 

무조건 3개의 벽을 세워야 하므로

빈칸 n개 중 3개를 순서 상관없이 고르는 조합으로 구현하고

큐로 구현한 BFS로 바이러스의 개수를 구한 뒤

안전 영역의 개수 = 빈칸 개수 - 바이러스의 개수 - 3

의 최댓값을 출력해주면 된다.

 

< C++ 코드 >

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, cnt, res, x, y, tmp;
int arr[8][8], dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
vector <pair<int, int>> zero, virus;
queue <pair<int, int>> q;
int Bfs(bool visited[][8]) {
	int count = 0;
	while (!q.empty()) {
		for (int i = 0; i < 4; i++) { //상하좌우
			x = q.front().first + dx[i], y = q.front().second + dy[i];
			if (x >= 0 && x < N && y >= 0 && y < M && arr[x][y] == 0 && visited[x][y] == false) {
				visited[x][y] = true;
				count++;
				q.push(make_pair(x, y));
			}
		}
		q.pop();
	}
	return count;
}
void Combination(int idx) {
	if (cnt == 3) { //벽을 세 개 세우면 BFS로 바이러스 개수 구함
		bool visited[8][8] = { false };
		tmp = 0;
		for (int i = 0; i < virus.size(); i++) {
			q.push(make_pair(virus[i].first, virus[i].second));
			tmp += Bfs(visited);
		}
		res = max(res, (int)zero.size() - 3 - tmp); //안전 영역의 최댓값 구함
		return;
	}
	for (int i = idx; i < zero.size(); i++) {
		arr[zero[i].first][zero[i].second] = 1, cnt++;
		Combination(i + 1);
		arr[zero[i].first][zero[i].second] = 0, cnt--;
	}
}

int main() {
	cin >> N >> M;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			cin >> arr[n][m];
			if (!arr[n][m]) zero.push_back(make_pair(n, m)); //빈칸인 애들만 모아줌
			else if (arr[n][m] == 2) virus.push_back(make_pair(n, m)); //바이러스인 애들만 모아줌
		}
	}
	Combination(0);
	cout << res;
	return 0;
}

 

< JAVA 코드 >

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_14502_연구소 {
	static int N, M, res = 0;
	static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	static boolean visited[][];
	static ArrayList<int[]> vacancy = new ArrayList<>();
	
	static int bfs() {
		int cnt = 0;
		visited = new boolean[N][M];
		Queue<int[]> virus = new LinkedList<>();
		for(int i = 0; i < N; i++) { // 바이러스 있는 위치 담기, 방문 체크
			for(int j = 0; j < M; j++) {
				if(arr[i][j] == 2) {
					visited[i][j] = true;
					virus.offer(new int[] {i, j});
				}
			}
		}
		while(!virus.isEmpty()) {
			for(int i = 0; i < 4; i++) {
				int x = virus.peek()[0] + dx[i], y = virus.peek()[1] + dy[i];
				if(x < 0 || x >= N || y < 0 || y >= M || arr[x][y] == 1 || visited[x][y]) continue; // 범위를 벗어나거나 벽이거나 이미 방문한 경우 넘어
				visited[x][y] = true; // 방문 체크
				virus.offer(new int[] {x, y}); // 바이러스화 됐으므로 큐에 추가
				cnt++; // 바이러스화 된 빈 방 개수 카운트
			}		
			virus.poll();
		}
		return cnt;
	}
	
	static void combination(int idx, int cnt) { // 빈방인 애들 중 3개씩만 골라서 벽 세우기
		if(cnt == 3) {
			res = Math.max(res, vacancy.size() - bfs() - 3); // 남은 빈 방 개수 중 최대값 갱신
			return;
		}
		for(int i = idx; i < vacancy.size(); i++) {
			arr[vacancy.get(i)[0]][vacancy.get(i)[1]] = 1; // 벽 세우기
			combination(i + 1, cnt + 1);
			arr[vacancy.get(i)[0]][vacancy.get(i)[1]] = 0; // 재귀에서 돌아오면 빈 방으로 바꿔주기
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		arr = new int[N][M];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
				if(arr[i][j] == 0) vacancy.add(new int[] {i, j}); // 빈 방인 애들 위치 넣어두기
			}
		}
		combination(0, 0);
		System.out.println(res);
	}
}