[BOJ] 14502번 연구소

문제

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

14502번: 연구소

 

 

풀이

이 문제는 BruteForce와 DFS가 합쳐진 문제이다. 빈칸에 벽을 세울 수 있는 모든 경우의 수마다 바이러스가 퍼질 수 있는 공간을 채워가며 안전 영역을 구하면 된다.

벽을 세우는 경우의 수를 구하는 함수에서 바이러스 있는 곳의 좌표와 함께 사용되므로 4중 포문이 쓰여서 다소 깔끔하지 않고 효율성은 떨어지는 코드이지만 추후에 더 효율적인 방법을 알게 된다면 수정해서 올려야겠다.

 

 

import java.util.*;
 
class Point {
    int row;
    int col;
    
    public Point(int row, int col) {
        this.row = row;
        this.col = col;
    }
}
 
public class Main {
    static Scanner scan = new Scanner(System.in);
    static int[] r = { -1, 1, 0, 0 };
    static int[] c = { 0, 0, -1, 1 };
    static int[][] lab, tmp;
    static Vector<Point> virus, safe;
    static int Max = -1;
    static int N, M;
 
    static void init() {
        N = scan.nextInt();
        M = scan.nextInt();
        lab = new int[N][M];
        tmp = new int[N][M];
        virus = new Vector<Point>();
        safe = new Vector<Point>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                lab[i][j] = scan.nextInt();
                if (lab[i][j] == 2)
                    virus.add(new Point(i, j));
                if (lab[i][j] == 0)
                    safe.add(new Point(i, j));
            }
        }
        copy_lab();
    }
 
    static void install() {
        int len = safe.size();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i != j) {
                    for (int k = 0; k < len; k++) {
                        if (i != k && j != k) {
                            tmp[safe.get(i).row][safe.get(i).col] = 1;
                            tmp[safe.get(j).row][safe.get(j).col] = 1;
                            tmp[safe.get(k).row][safe.get(k).col] = 1;
 
                            for (int l = 0; l < virus.size(); l++)
                                virus_dfs(virus.get(l).row, virus.get(l).col);
                            Max = Math.max(Max, get_safe());
                            copy_lab();
                        }
                    }
                }
            }
 
        }
    }
 
    static void virus_dfs(int row, int col) {
        for (int i = 0; i < 4; i++) {
            if (is_valid(row + r[i], col + c[i])) {
                tmp[row + r[i]][col + c[i]] = 2;
                virus_dfs(row + r[i], col + c[i]);
            }
        }
    }
 
    static boolean is_valid(int row, int col) {
        if ((row >= 0 && row < N) && (col >= 0 && col < M) && tmp[row][col] != 1 && tmp[row][col] != 2)
            return true;
        return false;
    }
 
    static int get_safe() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tmp[i][j] == 0)
                    cnt++;
            }
        }
        return cnt;
    }
 
    static void copy_lab() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                tmp[i][j] = lab[i][j];
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        install();
        System.out.println(Max);
    }
}