[백준 풀이_Java] 14502 연구소 (골드4)

 

복잡한 구현문제는 속도를 신경쓰기전에 일단 구현하는 것이 관건이다.

 

이 문제는 dfs, 백트래킹을 모두 사용하는 구현문제였다.

 

어렵당,,

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;


public class Main {

    static int sero;
    static int garo;
    static int[][] board;
    static int[][] moves = {{-1,0}, {1,0}, {0,1}, {0,-1}}; //위 아래 오른 왼
    static StringBuilder sb = new StringBuilder();
    static Queue<int[]> virus = new LinkedList<>();
    static HashSet<Integer> result = new HashSet<>();

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        sero = Integer.parseInt(input[0]);
        garo = Integer.parseInt(input[1]);
        board = new int[sero][garo];

        for(int i=0; i<sero; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<garo; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        addBoard(0);
        System.out.println(Collections.max(result));

    }

    private static void addBoard(int cntB) {
    
        if(cntB == 3) {
            spreadVirus();
        }else{
            for (int i = 0; i<sero; i++){
                for(int j=0; j<garo;j++){
                    if(board[i][j] == 0){
                        board[i][j] = 1;
                    //    System.out.println("i:"+i+",j:"+j);
                        addBoard(cntB+1);
                        board[i][j] = 0;
                    }
                }
            }
        }

    }


    public static void spreadVirus() {

        int[][] cpymap = new int[sero][garo];
        for (int i=0;i<sero;i++){
            for(int j=0;j<garo;j++){
                cpymap[i][j] = board[i][j];
                if(cpymap[i][j] == 2) {
                    virus.add(new int[]{i,j});
                }
            }
        }

        while (!virus.isEmpty()){
            int[] vi = virus.remove();
            for(int[]move : moves){
                int i = vi[0] + move[0];
                int j = vi[1] + move[1];
                if(i>=0 && j>=0 && i<sero && j<garo && cpymap[i][j]==0){
                    cpymap[i][j] = 2; // 바이러스 침투
                    virus.add(new int[]{i,j});
                }
            }
        }
        safeArea(cpymap);
    }


    public static void safeArea(int[][]cpymap){
    
        int safe = 0;
        for (int i=0;i<sero;i++){
            for(int j=0;j<garo;j++){
                if(cpymap[i][j] == 0) safe++;
            }
        }
        result.add(safe);
    }

}