반응형
출처: https://www.acmicpc.net/problem/14502
Input
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
Output
27
① 벽을 세우지 않았다면 모든 빈 칸(0)에 바이러스가 퍼져나갈 수 있습니다.
② 하지만 3 곳에 벽을 세워서
※ 새로 세울 수 있는 벽의 개수는 3개이면 반드시 모두 세워야 합니다.
③ 바이러스가 퍼질 수 없는 안전 영역을 확보하였습니다.
이처럼, 안전 영역 크기의 최댓값을 구하시오.
구현 사항
① 3개의 벽을 세우는 경우의 수를 모두 구합니다. ← 조합
② 경우의 수마다 바이러스 확산 후 안전영역 크기를 구합니다. ← BFS
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int M, N;
static int[][] arr;
static int[][] temp;
static int answer = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = Integer.parseInt(sc.next());
M = Integer.parseInt(sc.next());
arr = new int[N+1][M+1];
// 임시용도로 복사배열이므로 크기는 동일하게
temp = new int[N+1][M+1];
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
arr[i][j] = Integer.parseInt(sc.next());
}
}
makeWall(0);
System.out.println(answer);
}
static void makeWall(int cnt) {
if(cnt == 3) {
infection();
return;
}
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
if(arr[i][j] == 0) {
arr[i][j] = 1; // (cnt+1)번째 벽을 세운 곳
makeWall(cnt + 1); // 재귀
arr[i][j] = 0;
}
}
}
}
static void infection() {
// 상,하,좌,우
int[] rows = {-1, 1, 0, 0};
int[] cols = {0, 0, -1, 1};
Queue<Node> queue = new LinkedList<>();
// 최초 전염지점을 큐에 담는다.
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
// 각 case 바이러스 전파 확인용 임시 복사배열
temp[i][j] = arr[i][j];
if(arr[i][j] == 2) { // 바이러스 지점이라면
queue.add(new Node(i, j));
} // 최초의 바이러스 지점은 각 case마다 동일하긴 하지만 BFS를 위해 그때그때 다시 넣어준다.
}
}
// 최초 지점들로 부터 모두 전염시킨다.
while(!queue.isEmpty()) {
Node curNode = queue.poll();
// 상하좌우 확인
for(int i=0; i<4;i++) {
int infect_x = curNode.x + rows[i];
int infect_y = curNode.y + cols[i];
// 기존에 전염되지 않았고 벽이 아니라면
if(infect_x < 1 || infect_y < 1) continue;
if(infect_x > N || infect_y > M) continue;
if(temp[infect_x][infect_y] == 0) {
temp[infect_x][infect_y] = 2; // 전염표시
queue.add(new Node(infect_x, infect_y));
}
}
}
checkSafetyArea();
}
private static void checkSafetyArea() {
int count = 0;
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
if(temp[i][j] == 0) {
count++;
}
}
}
answer = Math.max(answer, count);
}
}
class Node{
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
반응형
'PS 문제 풀이 > Baekjoon' 카테고리의 다른 글
[BOJ] 백준 14501 퇴사 (0) | 2021.02.21 |
---|---|
[BOJ] 백준 14500 테트로미노 (0) | 2021.02.21 |
[BOJ] 백준 14499 주사위 굴리기 (1) | 2021.02.21 |
[BOJ] 백준 3190 뱀 (0) | 2021.02.21 |
[BOJ] 백준 12100 2048(Easy) (0) | 2021.02.21 |
댓글