문제
https://www.acmicpc.net/problem/14502
풀이
1. 백트래킹을 이용하여 promising() (상,하,좌,우 또는 대각선에 벽 또는 바이러스가 있는지 검사하는 함수)가 true로 반환되면 벽(1)을 세우고 벽이 3개 세워질때까지 반복한다.
2. 벽이 3개 세워지면 bfs() 함수를 통해 바이러스 침투 경로를 확인하고, 안전한 공간의 갯수를 카운트 센 다음, max값이랑 비교 후 max값 대체
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;
import java.util.StringTokenizer;
class Node {
int a, b;
Node(int a, int b) {
this.a = a;
this.b = b;
}
public int getA() {
return a;
}
public int getB() {
return b;
}
}
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int[][] dxdy = {{-1,1}, {1,1}, {-1,-1}, {1,-1}};
static int[][] map;
static int n;
static int m;
static int max = Integer.MIN_VALUE;
public static void main(String args[]) throws IOException {
String[] inputs;
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
inputs = bf.readLine().split(" ");
n = Integer.parseInt(inputs[0]);
m = Integer.parseInt(inputs[1]);
map = new int[n][m];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(max);
}
// 백트래킹
static void dfs(int cnt) {
if (cnt == 3) {
bfs();
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] != 1 && map[i][j] != 2 && promising(i, j)) {
map[i][j] = 1;
dfs(cnt + 1);
map[i][j] = 0;
}
}
}
}
// 주변에 벽이 1개이상 있거나, 바이러스가 있을 시 유망하다고 판단
static boolean promising(int a, int b) {
int x, y;
boolean check = false;
// 상하좌우
for (int i = 0; i < 4; i++) {
x = a + dx[i];
y = b + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m) {
if (map[x][y] == 1 || map[x][y] == 2){
check = true;
break;
}
}
// 대각선
for(int j = 0; j < 4; j++){
x = a + dxdy[j][0];
y = b + dxdy[j][1];
if (x >= 0 && x < n && y >= 0 && y < m) {
if (map[x][y] == 1 || map[x][y] == 2){
check = true;
break;
}
}
}
}
return check;
}
// 바이러스 감염 bfs로 구현
static void bfs() {
int[][] map_ = map;
int cnt = 0;
int[][] tmp_map = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++) {
tmp_map[i][j] = map[i][j];
}
}
Node node;
Queue<Node> q = new LinkedList<>();
// 바이러스 감염 처리
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(tmp_map[i][j] == 2){
node = new Node(i, j);
q.offer(node);
while(!q.isEmpty()){
node = q.poll();
for(int k = 0; k < 4; k++){
int x = dx[k] + node.getA();
int y = dy[k] + node.getB();
if (x >= 0 && x < n && y >= 0 && y < m) {
if(tmp_map[x][y] != 1 && tmp_map[x][y] != 2){
tmp_map[x][y] = 2;
q.offer(new Node(x, y));
}
}
}
}
}
}
}
// 안전지역 카운트
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(tmp_map[i][j] == 0)
cnt++;
}
}
max = Math.max(cnt, max);
}
}
'Algorithm > BaekJoon' 카테고리의 다른 글
[그리디/우선순위 큐] 백준 11000 강의실 배정 풀이 (0) | 2022.07.22 |
---|---|
[BFS/구현] 백준 16236 아기상어 풀이 (0) | 2022.05.26 |
[완전탐색] 백준 1051 숫자 정사각형 풀이 (0) | 2022.03.29 |
[BFS] 백준 1012 유기농 배추 풀이 (0) | 2022.03.21 |
[재귀] 백준 2331 반복수열 풀이 (0) | 2022.03.10 |