[baekjoon]14502 연구소 java

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

14502번: 연구소

벽을 3개만 세울 수 있다는 것과 크기를 봤을 때, 백트래킹으로 모든 경우의 수를 구해서 풀이해도 될거라는 생각이 들었다.

따라서 백트래킹을 이용하여 모든 조합을 구해주었고, 그 값들을 벽으로 바꾼 후,

BFS를 이용하여 전부 탐색을 해주었다.(DFS도 상관없음)

벽으로 바꾼 값들은 다시 돌려주어서 다른 경우에도 사용할 수 있도록 해주어야한다.

안전 지역을 파악하는 것때문에 전체 for문을 돌려서 안전한 곳만 파악해주었다.

전반적으로 백트래킹의 개념 원리가 많이 들어가 있는 듯한 문제.

 

//https://www.acmicpc.net/problem/14502
import java.io.*;
import java.util.*;
 
/**
 * 벽 3개만 새우기... DFS이용해도 될 것 같고 숫자가 크지 않기에 백트래킹으로 모든 경우의 수 만들어도 될 것 같기도 하다.
 **/
class Main {
    static boolean[] marked;
    static int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 북 동 남 서
    static int N, M, answer;
    static int[][] map;
    static int[] arr;
    static ArrayList<Dot> wallList;
 
    public static void main(String[] args) throws Exception {
        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());
        map = new int[N][M];
        arr = new int[3];
        wallList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int cur = Integer.parseInt(st.nextToken());
                map[i][j] = cur;
                if(cur == 0) wallList.add(new Dot(i, j));
            }
        }
        marked = new boolean[wallList.size()];
        combi(0, 0);
        System.out.println(answer);
    }
 
    public static int safetyArea() {
        boolean[][] virusArea = new boolean[N][M];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 2) {
                    virusArea[i][j] = true;
                    Queue<Dot> queue = new LinkedList<Dot>();
                    queue.add(new Dot(i, j));
                    while(!queue.isEmpty()) {
                        Dot cur = queue.poll();
                        
                        for (int k = 0; k < 4; k++) {
                            int nextR = cur.row + dirs[k][0];
                            int nextC = cur.col + dirs[k][1];
                            
                            if(nextR < 0 || nextC < 0 || nextR >= N || nextC >= M) continue;
                            if(map[nextR][nextC] != 0) continue;
                            if(virusArea[nextR][nextC]) continue;
                            
                            virusArea[nextR][nextC] = true;
                            queue.add(new Dot(nextR, nextC));
                        }
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 0 && !virusArea[i][j]) max++;
            }
        }
        return max;
        
    }
    
    public static void combi(int curCnt, int startIdx) {
        if (curCnt == 3) {
            for (int x : arr) {
                Dot dot = wallList.get(x);
                map[dot.row][dot.col] = 1;
            }
 
            answer = Math.max(answer, safetyArea());
 
            for (int x : arr) {
                Dot dot = wallList.get(x);
                map[dot.row][dot.col] = 0;
            }
            return;
        }
 
        for (int i = startIdx; i < wallList.size(); i++) {
            if (marked[i])
                continue;
            marked[i] = true;
            arr[curCnt] = i;
            combi(curCnt + 1, i + 1);
            marked[i] = false;
        }
    }
}
 
class Dot {
    int row;
    int col;
 
    Dot(int row, int col) {
        this.row = row;
        this.col = col;
    }
}