[Java] 14502 연구소

1. 문제 링크 및 문제

https://www.acmicpc.net/problem/14502

1-1 문제 요약

: N*M 의 연구소에서 2 근처에 벽을 3개 세워 퍼지는 것을 최대한 막는 문제, 1의 최대 개수를 구하는 문제

2. 해결 방법 생각해보자 ...

1. makeWall() : '2' 옆에 서로다른 3개의 벽을 만들기
   1-1. 서로다른 3개의 벽을 만들 때 -> BFS 사용
2. bfs() : (0,0)부터 (N,M)의 값이 '2'일 때, 상하좌우 좌표값==0 이면 2 (=바이러스 퍼짐) -> BFS 사용
3. findSafe() : 0 의 개수를 구한다 (=안전구역 구함)
4. 1-2-3 반복

3. 코드

import java.util.*;
import java.io.*;
import java.awt.Point;

public class Main {

    static int[][] map ;
    static boolean[][] visited;
    static int N,M;
    static int MaxSafeZone = Integer.MIN_VALUE;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static Queue<Point> que = new LinkedList<>();

    public static void main(String[] args) throws Exception{

        // 값 입력받기 -- >
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M];

		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());
			}
		}
        // <-- 값 입력받기

        //3개의 다른 벽 세우기
        MakeWall(0);

        System.out.println(MaxSafeZone);

    }

    public static void MakeWall(int count){
        if (count == 3){
            bfs();
            return;
        }

        for(int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if(map[i][j] == 0){
                    map[i][j] = 1;
                    MakeWall(count +1);
                    map[i][j] = 0 ;
                }
            }
        }
    }

    public static void bfs(){
        int[][] CopyMap = new int[N][M];

        // 2 전염시킬 맵 복사하여 생성 (원래맵은 벽 생성에 써야함.)
        for(int i=0;i<N;i++){CopyMap[i] = map[i].clone();}

        // --> 2 일 때, 큐에 넣기 
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(CopyMap[i][j] == 2 ){
                    que.offer(new Point(i,j));            
                }
            }
        }
        // <-- 
        
        // --> 2 주변 전염시키기
        while(!que.isEmpty()){
            Point now = que.poll();
            for(int k=0;k<4;k++){
                int xx = now.x+dx[k];
                int yy = now.y+dy[k];
                if(xx<0 || xx>=N || yy<0 || yy>=M ) continue;
                if(CopyMap[xx][yy] == 0){
                    que.offer(new Point(xx,yy));
                    CopyMap[xx][yy] = 2; 
                }
            }    
        }
        // <-- 

        // 전염시킨 후, 0 인 구간 세기
        FindSafe(CopyMap);
    }

    public static void FindSafe(int[][] CopyMap){
        int SafeZone = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if (CopyMap[i][j] == 0){
                    SafeZone += 1;
                }
            }
        }
        MaxSafeZone = Math.max(MaxSafeZone, SafeZone);
    }

}