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

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

14502번: 연구소

 

벽을 세울 수 있는 곳을 미리 저장하고 조합으로 벽을 하나하나 세우면서 계산하는 문제이다. BFS를 사용할 때 바이러스의 위치를 저장해 놓았다가 한번에 넣으면 쾌적하다. 점수 계산을 위해 배열을 복사하기도 하던데 그럴 필요 없이 전체에서 바이러스 확산 범위만큼 빼주면 계산할 수 있다.

 

 

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int input = Integer.parseInt(st.nextToken());
                map[i][j] = input;
                if (input == 0)
                    zeroList.add(new Point(i, j));
                else if (input == 2)
                    virusList.add(new Point(i, j));
            }
        }
        comb(0, 0);
        System.out.println(max);
    }

    static int N, M, map[][], numbers[] = new int[3], max = 0, dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
    static ArrayList<Point> zeroList = new ArrayList<>(), virusList = new ArrayList<>();

    static void bfs() {
        int count = 3; //벽 3개를 추가해서 추가로 빼줘야 함
        boolean visited[][] = new boolean[N][M];
        Deque<Point> q = new LinkedList<>();
        for (Point v : virusList) {
            q.add(v);
            visited[v.row][v.col] = true;
        }
        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur.row + dr[d];
                int nc = cur.col + dc[d];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M || map[nr][nc] == 1 || visited[nr][nc])
                    continue;
                q.add(new Point(nr, nc));
                visited[nr][nc] = true;
                count++;
            }
        }
        max = Math.max(zeroList.size() - count, max);
    }

    static void comb(int count, int start) {
        if (count == 3) {
            for (int n : numbers)
                map[zeroList.get(n).row][zeroList.get(n).col] = 1;
            bfs();
            for (int n : numbers)
                map[zeroList.get(n).row][zeroList.get(n).col] = 0;
            return;
        }
        for (int i = start; i < zeroList.size(); i++) {
            numbers[count] = i;
            comb(count + 1, i + 1);
        }
    }

    static class Point {
        int row, col;

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