14502. 연구소

문제 개요

특정 위치에 벽이라는 요소가 추가되었을 때 최대로 얻을 수 있는 빈 공간의 크기를 구하는 문제입니다.

문제 접근

맵의 최대 크기가 8x8크기이고 3개의 벽을 세울 수 있는 경우의 수는 ₆₄C₃=41,664 이므로 크기가 작아 부르트포스로 해결할 수 있었습니다.

코드는 빈 공간 중 3개의 위치를 차례대로 선택하고 바이러스가 있는 위치에서 BFS를 통해 감염된 부분들을 구하였습니다. 그리고 빈 공간의 크기에서 바이러스가 있는 크기를 뺀 값 중 가장 큰 값을 출력하도록 하였습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

class Pos{
    private int row;
    private int col;

    public Pos(int row, int col){
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Pos other = (Pos)obj;
        return row == other.row && col == other.col;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, col);
    }
}

public class Main {
    static int N, M;
    static int[][] labatory;

    static final int[][] dirs = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}
    };

    static void input() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = bf.readLine().split(" ");
        N = Integer.parseInt(firstLine[0]);
        M = Integer.parseInt(firstLine[1]);
        labatory = new int[N][];
        for(int i=0;i<N;i++){
            labatory[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
    }

    static boolean isIn(int row, int col){
        return row >= 0 && row < N && col >= 0 && col < M;
    }

    static int getProtects(List<Pos> freeSpaces, List<Pos> virus){
        int inspectedSpaces = 0;
        boolean[][] isVisited = new boolean[N][M];

        for(int i=0;i<virus.size();i++){
            //BFS
            Queue<Pos> q = new LinkedList<>();
            q.add(virus.get(i));
            isVisited[virus.get(i).getRow()][virus.get(i).getCol()] = true;
            while(!q.isEmpty()){
                Pos cur = q.remove();
                for(int d=0;d<4;d++){
                    Pos next = new Pos(cur.getRow()+dirs[d][0], cur.getCol()+dirs[d][1]);
                    if(!isIn(next.getRow(), next.getCol())){
                        continue;
                    }
                    if(isVisited[next.getRow()][next.getCol()]){
                        continue;
                    }
                    if(labatory[next.getRow()][next.getCol()] != 0){
                        continue;
                    }
                    q.add(next);
                    isVisited[next.getRow()][next.getCol()] = true;
                    inspectedSpaces++;
                }
            }
        }
        //벽을 세울 3곳을 선택했으므로 3을 빼줌
        return (freeSpaces.size() - 3) - inspectedSpaces;
    }

    static void process(){
        List<Pos> freeSpaces = new ArrayList<>();
        List<Pos> virus = new ArrayList<>();
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(labatory[i][j] == 0){
                    freeSpaces.add(new Pos(i, j));
                }
                if(labatory[i][j] == 2){
                    virus.add(new Pos(i, j));
                }
            }
        }

        int protects = 0;
        for(int i=0;i<freeSpaces.size(); i++){
            labatory[freeSpaces.get(i).getRow()][freeSpaces.get(i).getCol()] = 1;
            for(int j=i+1;j<freeSpaces.size();j++){
                labatory[freeSpaces.get(j).getRow()][freeSpaces.get(j).getCol()] = 1;
                for(int k=j+1; k<freeSpaces.size(); k++){
                    labatory[freeSpaces.get(k).getRow()][freeSpaces.get(k).getCol()] = 1;

                    protects = Math.max(protects, getProtects(freeSpaces, virus));

                    labatory[freeSpaces.get(k).getRow()][freeSpaces.get(k).getCol()] = 0;
                }
                labatory[freeSpaces.get(j).getRow()][freeSpaces.get(j).getCol()] = 0;
            }
            labatory[freeSpaces.get(i).getRow()][freeSpaces.get(i).getCol()] = 0;
        }

        System.out.println(protects);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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