문제풀이
크기가 n과 m 인 연구소
2는 바이러스 1 은 벽 0 은 빈칸이다.
바이러스(2) 는 상하좌우로 번식한다 (0) 빈벽일때
벽 3 개를 세울때 가장 큰 값을 구한다
-
입력 n 과 m 을 입력 받고 바이러스 들을 입력 받는다.
-
벽 3 개를 둔다.
우선 처음 wall 0
각 배열을 돌면서 첫 오는 빈벽 0 을 만나면 1로 만들고 cnt ++
다음 오는 첫 빈벽 찻기
다시 1을 만든 빈벽 0 으로 두기
wall 가 3이면 영역 크기 찾기 (벽이 3 개 인 것이니)
(Dfs) -
영역 크기 찾기
2 인 것을 찾아서
다음 노드들 감염 시키기 -
모든 노드를 찾아서 0인 부분을 찾기
코드
- 벽 3개 두기
private static void dfs(int wall){
if(wall == 3){ // 벽이 3개일때
visited = new boolean[n][m];
copyArr = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
copyArr[i][j] = arr[i][j];
}
}
for(int i=0; i<n; i++){ // 감염 시키기
for(int j=0; j<m; j++){
if(copyArr[i][j] == 2){
if(!visited[i][j]){
bfs(i,j); // 모든 노드 2 를 만들기
}
}
}
}
// 안전 지대 찾기
int count = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(copyArr[i][j] == 0){
count++;
}
}
}
max = Math.max(max,count);
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(wall+1);
arr[i][j] = 0;
}
}
}
}- 감염 인접 노드 감염 시키기
private static void bfs(int x, int y){ // 다음 노드 감염 시키기
visited[x][y] = true;
Queue<Nodes> queue = new LinkedList();
queue.add(new Nodes(x,y));
while (!queue.isEmpty()){
Nodes nowNode = queue.poll();
int nowX = nowNode.x;
int nowY = nowNode.y;
// 다음 노드 가능 여부 및 탐색
for(int i=0; i<4; i++){
int nextX = nowX+dx[i];
int nextY = nowY +dy[i];
if(nextX >=0 && nextX <n){
if(nextY>=0 && nextY<m){
if(copyArr[nextX][nextY]==0){
if(!visited[nextX][nextY]){
visited[nextX][nextY] = true; // 다음 노드 방무
copyArr[nextX][nextY] = 2; // 다음 노드 감염
queue.add(new Nodes(nextX,nextY)); // 다음 노드 탐색
}
}
}
}
}
}
}전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class boj14502 {
private static int[][] arr;
private static int[][] copyArr;
private static boolean[][] visited;
private static int n;
private static int m;
private static int[] dx = {1,-1,0,0};
private static int[] dy = {0,0,1,-1};
private static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException{
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());
arr = new int[n][m];
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
} // 1. 배열 입력
dfs(0);
System.out.println(max);
}
private static void dfs(int wall){
if(wall == 3){ // 벽이 3개일때
visited = new boolean[n][m];
copyArr = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
copyArr[i][j] = arr[i][j];
}
}
for(int i=0; i<n; i++){ // 감염 시키기
for(int j=0; j<m; j++){
if(copyArr[i][j] == 2){
if(!visited[i][j]){
bfs(i,j); // 모든 노드 2 를 만들기
}
}
}
}
// 안전 지대 찾기
int count = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(copyArr[i][j] == 0){
count++;
}
}
}
max = Math.max(max,count);
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(wall+1);
arr[i][j] = 0;
}
}
}
}
private static void bfs(int x, int y){ // 다음 노드 감염 시키기
visited[x][y] = true;
Queue<Nodes> queue = new LinkedList();
queue.add(new Nodes(x,y));
while (!queue.isEmpty()){
Nodes nowNode = queue.poll();
int nowX = nowNode.x;
int nowY = nowNode.y;
// 다음 노드 가능 여부 및 탐색
for(int i=0; i<4; i++){
int nextX = nowX+dx[i];
int nextY = nowY +dy[i];
if(nextX >=0 && nextX <n){
if(nextY>=0 && nextY<m){
if(copyArr[nextX][nextY]==0){
if(!visited[nextX][nextY]){
visited[nextX][nextY] = true; // 다음 노드 방무
copyArr[nextX][nextY] = 2; // 다음 노드 감염
queue.add(new Nodes(nextX,nextY)); // 다음 노드 탐색
}
}
}
}
}
}
}
}
class Nodes{
int x;
int y;
public Nodes(int x, int y){
this.x = x;
this.y = y;
}
}bfs 와 dfs 를 합친 문제
허나 배열 복사 부분을 주의해 줘야 할 거 같다.
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
copyArr[i][j] = arr[i][j];
}
} // 주의 하기 