백준 14502 - 연구소(새 풀이)

백트래킹 + BFS

import java.util.*;

public class boj14502_연구소 {

    static int[] dy = {-1, 1,0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int N, M;
    static int[][] map, temp;
    static boolean[] visited;
    static LinkedList<Pair> pick = new LinkedList();
    static int result = 0;
    static int safeCount = 0;


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt(); // 세로
        M = sc.nextInt(); // 가로
        map = new int[N+1][M+1];
        temp = new int[N+1][M+1];
        int zeroCount = 0;


        for(int y = 1; y <= N;  y++){
            for(int x = 1; x <= M; x++){
                map[y][x] = sc.nextInt();
                if(map[y][x] == 0){
                    zeroCount++;
                }
            }
        }

        setting();
        visited = new boolean[zeroCount];
        DFS(0,0);
        System.out.println(result);



    }

    static void DFS(int start, int depth){

        if(depth == 3){
            tempMap();
//            spreadVirus();
            spreadVirus2();
            safeCount();

            result = Math.max(result, safeCount);
            return;
        }


        for(int i=start; i<pick.size(); i++){
            Pair pair = pick.get(i);

            int ny = pair.y;
            int nx = pair.x;

            if(visited[i] == false){
                map[ny][nx] = 1;
                visited[i] = true;
                DFS(i+1, depth+1);
                visited[i] = false;
                map[ny][nx] = 0;
            }


        }


    }

    static void spreadVirus() {

        Queue<Pair> queue = new LinkedList<>();

        for(int y=1; y<=N; y++){
            for(int x=1; x<=M; x++){
                if(temp[y][x] == 2 ){
                    queue.add(new Pair(y,x));
                }
            }
        }

        while(!queue.isEmpty()){
            Pair t = queue.poll();

            for(int i=0; i<4; i++) {
                int ny = t.y+ dy[i];
                int nx = t.x+ dx[i];
                if(ny <1 || nx <1 || ny>N || nx >M) continue;
                if(temp[ny][nx] == 1) continue;
                if(temp[ny][nx] == 0){
                    temp[ny][nx] = 2;
                    queue.add(new Pair(ny,nx));
                }
            }
        }


    }

    static void safeCount(){
        safeCount = 0;
        for(int y = 1; y <= N;  y++){
            for(int x = 1; x <= M; x++){
                if(temp[y][x] == 0){
                    safeCount++;
                }
            }
        }

    }

    static void tempMap(){
        for(int y = 1; y <= N;  y++){
            for(int x = 1; x <= M; x++){
                temp[y][x] = map[y][x];
            }
        }
    }

    static void setting(){

        Pair pair;
        for(int y = 1; y <= N;  y++){
            for(int x = 1; x <= M; x++){
                temp[y][x] = map[y][x];

                if(map[y][x] == 0){
                    pair = new Pair(y,x);
                    pick.add(pair);
                }
            }
        }

    }

    static class Pair{
        int y;
        int x;

        Pair(int a, int b){
            this.y = a;
            this.x = b;
        }
    }

    static void spreadVirus2(){

        Queue<Pair> queue = new LinkedList<>();

        for(int y=1; y<=N; y++){
            for(int x=1; x<=M; x++){
                if(temp[y][x] == 2){
                    queue.add(new Pair(y,x));
                }
            }
        }

        while(!queue.isEmpty()){

            Pair pair = queue.poll();

            for(int i=0; i<4; i++){
                int ny = pair.y + dy[i];
                int nx = pair.x + dx[i];

                if(ny>=1 && ny <=N && nx >=1 && nx<=M){
                    if(temp[ny][nx] == 0){
                        temp[ny][nx] = 2;
                        queue.add(new Pair(ny,nx));
                    }
                }
            }

        }

    }
}