백준 14502번
https://www.acmicpc.net/problem/14502
문제
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
예제 입력
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0예제 출력
27생각하기
DFS와 BFS를 모두 사용하는 문제이다.
DFS는 백트래킹을 사용해서 푸는 문제이고,
BFS는 일반 Queue를 통해 노드를 탐색하면 된다.
DFS 백트래킹을 사용하는 이유는 벽을 세우며 안전영역 최대값을 찾기 위해서는 세웠던 벽을 없애고 다시 새로운 벽을 세우는 과정이 필요하므로 1이었던 부분을 0으로 바꾸는 과정이 들어가게된다.
BFS는 안전영역을 탐색해서 count를 하는 과정이다.
동작
class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
} // End of Node
public class Main {
static int dirX[] = {0, 0, -1, 1};
static int dirY[] = {-1, 1, 0, 0};
static int arr[][];
static int result = Integer.MIN_VALUE / 16;
static int nowX, nowY, N, M;노드 탐색을 위해 만들어 놓은 변수와 class 입니다.
상 하 좌 우 탐색을 할 수 있는 dirX, diry 배열이 있습니다.
reuslt가 Integer.MIN_VALUE / 16 을 해두는 이유는 최대값에서 오버플로우가 발생하는 것을 방지하기 위함입니다. 크게 이유는 없습니다.
// 벽을 세우는 작업
static void DFS(int depth) {
if(depth == 3) {
BFS();
return;
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(arr[i][j] == 0) {
arr[i][j] = 1;
DFS(depth + 1);
arr[i][j] = 0;
}
}
}
} // End of DFS백트래킹 과정입니다. depth는 벽의 숫자를 의미하고 벽의 숫자가 3개가 됬을 때,
BFS탐색을 시작합니다.
arr전체를 탐색하여 0인 공간에 모두 벽을 세워봅니다.
벽을 세웠던 공간은 새로운 벽을 위해 철거하는 과정인 백트래킹을 사용합니다.
마지막에 arr[i][j] = 0;을 하는 이유입니다.
static void BFS() {
int map[][] = new int[N][M];
Queue<Node> que = new LinkedList<>();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
map[i][j] = arr[i][j];
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == 2) {
que.offer(new Node(i, j));
}
}
}
while(!que.isEmpty()) {
Node node = que.poll();
for(int i=0; i<4; i++) {
nowX = node.x + dirX[i];
nowY = node.y + dirY[i];
if(Range_check() && map[nowX][nowY] == 0) {
map[nowX][nowY] = 2;
que.offer(new Node(nowX, nowY));
}
}
}
find_max(map);
}BFS로 탐색하여 2를 점점 퍼트려서 퍼질 수 있는 공간을 모두 채웁니다.
배열에 더 이상 2를 채울 수 없으면, que를 순회해서 0의 숫자를 세아려 최대값을 갱신합니다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N, M, result;
static int[][] map, tempMap;
static boolean[][] isVisited = new boolean[N][M];
static int[] dirX = {-1, 1, 0, 0};
static int[] dirY = {0, 0, -1, 1};
static List<Coordinates> virusCorList; // 바이러스 좌표값
static List<Coordinates> safetyCorList; // 안전구역 좌표값
static Coordinates[] comb;
static class Coordinates {
int x;
int y;
public Coordinates(int x, int y) {
this.x = x;
this.y = y;
}
} // End of Coordinates class
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
init();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
tempMap[i][j] = map[i][j];
if (map[i][j] == 2) {
virusCorList.add(new Coordinates(i, j));
} else if (map[i][j] == 0) {
safetyCorList.add(new Coordinates(i, j));
}
}
}
DFS(0, safetyCorList.size(), 0);
System.out.println(result); // 안전영역의 최댓값
} // End of main
private static void DFS(int depth, int safetyZoneSize, int index) { // 벽을 세우는 경우의 수를 만들기.
if (depth == 3) {
for (Coordinates cor : comb) { // 만든 조합으로 벽세우기
tempMap[cor.x][cor.y] = 1;
}
isVisited = new boolean[N][M];
for (Coordinates cor : virusCorList) {
BFS(cor.x, cor.y);
}
int sum = countingAndCopy(); // 복사를 하면서 안전구역 숫자 세기
result = Math.max(result, sum);
return;
}
for (int i = index; i < safetyZoneSize; i++) {
comb[depth] = safetyCorList.get(i);
DFS(depth + 1, safetyZoneSize, i + 1);
}
} // End of DFS
private static void BFS(int x, int y) { // 바이러스 퍼트리기
Queue<Coordinates> que = new LinkedList<>();
que.offer(new Coordinates(x, y));
while (!que.isEmpty()) {
Coordinates cor = que.poll();
for (int i = 0; i < 4; i++) {
int nowX = cor.x + dirX[i];
int nowY = cor.y + dirY[i];
if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && tempMap[nowX][nowY] == 0) {
isVisited[nowX][nowY] = true;
tempMap[nowX][nowY] = 2; // 바이러스 퍼트림.
que.offer(new Coordinates(nowX, nowY));
}
}
}
} // End of BFS
private static boolean rangeCheck(int nowX, int nowY) {
return nowX >= 0 && nowX < N && nowY >= 0 && nowY < M;
} // End of rangeCheck
private static int countingAndCopy() {
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tempMap[i][j] == 0) {
sum++;
}
tempMap[i][j] = map[i][j];
}
}
return sum;
} // End of copy
private static void init() {
map = new int[N][M];
tempMap = new int[N][M];
result = Integer.MIN_VALUE;
virusCorList = new ArrayList<>();
safetyCorList = new ArrayList<>();
comb = new Coordinates[3];
} // End of init
} // End of Main class
