[백준] 14502번. 연구소(JAVA)

문제

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

---

풀이(21분)

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

    static int n,m;
    static int[][] arr;
//    static int[][] visited;
    static int[][] direction = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
    static ArrayList<Point> blankList = new ArrayList<>();
    static ArrayList<Point> virusList = new ArrayList<>();
    static Queue<Point> queue = new LinkedList<>();
    static int count;


    public static void main(String[] args) throws IOException {
        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());
        arr = new int[n][m];

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 0){
                    count++;
                    blankList.add(new Point(i,j));
                } else if (arr[i][j] == 2) {
                    virusList.add(new Point(i,j));
                }
            }
        }

        int defaultCount = count;
        int answer = 0;

        int size = blankList.size();
        for(int i = 0; i < size; i++){
            Point firstPoint = blankList.get(i);
            arr[firstPoint.x][firstPoint.y] = 1;
            for(int j = i+1; j < size; j++){
                Point secondPoint = blankList.get(j);
                arr[secondPoint.x][secondPoint.y] = 1;
                for(int k = j+1; k < size; k++){
                    Point thirdPoint = blankList.get(k);
                    arr[thirdPoint.x][thirdPoint.y] = 1;
                    queue.addAll(virusList);
                    count = defaultCount;
                    bfs();
                    if(count - 3 > answer){
                        answer = count - 3;
                    }
                    arr[thirdPoint.x][thirdPoint.y] = 0;
                }
                arr[secondPoint.x][secondPoint.y] = 0;
            }
            arr[firstPoint.x][firstPoint.y] = 0;
        }
        System.out.println(answer);
    }

    public static void bfs(){
        int[][] tempArr = new int[n][m];
        for (int i = 0; i < n; i++) {
            tempArr[i] = arr[i].clone(); // arr 배열 복사
        }

        while (!queue.isEmpty()){
            Point point = queue.poll();
            int row = point.x;
            int col = point.y;

            for (int i = 0; i < 4; i++) {
                int nextRow = row + direction[i][0];
                int nextCol = col + direction[i][1];

                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m) {
                    if (tempArr[nextRow][nextCol] == 0) {
                        tempArr[nextRow][nextCol] = 2;
                        count--;
                        queue.add(new Point(nextRow, nextCol));
                    }
                }
            }
        }
    }

}

 

풀이 방법은 간단하다. 조합을 통해 벽을 설치할 수 있는 모든 경우에 수에 대해 bfs를 실행하여 안전 구역의 최댓값을 구하는 것이다.

배열을 반복해서 쓸 것이기 때문에 배열을 직접 건드리는 것보다는 bfs에서는 temp배열을 사용하는 것으로 했다.

 

물론 깔끔하지는 않은 풀이일 수 있지만 메모리와 시간 제한에 문제가 없을 것이라고 생각했다.

 

메모리 제한은 512mb이며 시간제한은 2초였다. 다만, n과 m의 최댓값이 8이었기 때문에 시간 제한에 문제가 없었다.

조합을 만들어내는 최악은 (nxm)^3이다. 여기에 바이러스를 전파시키는 bfs를 생각하면 nxm이 한번 더 들어갔다. 즉 8x8의 4제곱이 되었고, 2^24이라고 대략 계산했기에 문제가 없을 것이라고 진행했고, 통과할 수 있었다.