[시뮬레이션] 연구실

백준 14502번 연구실 (삼성 SW역량테스트 기출)

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int M;
    static int[][] map;

    static int[] dn = {-1, 0, 1, 0};
    static int[] dm = {0, 1, 0, -1};

    static List<Position> ground = new ArrayList<>();
    static Queue<Position> virus = new LinkedList<>();

    static int maxValue=0;
    static int zeroCount=0;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N+1][M+1];

        //인풋
        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());

            for(int j=1; j<=M; j++){
                int pos = Integer.parseInt(st.nextToken());
                map[i][j] = pos;
                if(pos==0) ground.add(new Position(i,j));
                if(pos==2) virus.offer(new Position(i,j));
            }
        }


        zeroCount = ground.size();
        combination(zeroCount, 3, new int[3], 0, 0);

        System.out.println(maxValue);
    }


    //입력받은 지도에서 바이러스를 배양하고 빈칸을 측정
    static void bfs(int[][] nMap){

        //바이러스
        Queue<Position> q = getStartPoint();
        int ground = zeroCount-3; //처음 센 0개수에서 건설된 벽 3개 제외

        while ( !q.isEmpty() ){

            int qSize = q.size();
            for(int i=0; i<qSize; i++){

                Position now = q.poll();

                //4방향
                for(int j=0; j<4; j++){
                    Position next = new Position(now.n+dn[j], now.m+dm[j]);

                    if( isCanGo(next, nMap) ){
                        q.offer(next);
                        nMap[next.n][next.m] = 2;
                        ground--;
                    }
                }
            }//for(i)

            //더 해봤자 안됨 나가리
            if(ground < maxValue) break;
        }


        //남은 땅으로 정산
        maxValue = Math.max(maxValue, ground);
    }

    //갈 수 있는 땅인가
    static boolean isCanGo(Position p, int[][] nMap){

        //맵 안인지 확인
        if(p.n < 1 ||  N < p.n || p.m < 1 || M < p.m) return false;

        //갈 수 있는 땅인지
        if(nMap[p.n][p.m] != 0) return false;

        return true;
    }

    //3개의 숫자를 선택
    static void combination(int n, int r, int[] arr, int index, int target){

        if(r==0){
            bfs( makeWall(arr) );
        }
        else if(target==n) return;
        else{
            arr[index] = target;
            combination(n,r-1, arr, index+1, target+1);
            combination(n,r, arr, index, target+1);
        }
    }


    static void printMap(int[][] map){

        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                System.out.printf("%d ", map[i][j]);
            }
            System.out.println();
        }
    }

    static Queue<Position> getStartPoint(){

        Queue<Position> nQ = new LinkedList<>();
        for(Position v: virus){
            nQ.offer(v);
        }
        return nQ;
    }

    //3개의 벽을 건설된 맵을 리턴
    static int[][] makeWall(int[] walls){

        int[][] nMap = mapCopy();

        //벽 건설
        for(int i=0; i<3; i++){
            Position p = ground.get( walls[i] );
            nMap[p.n][p.m] = 1;
        }

        return nMap;
    }

    //맵의 복사본을 리턴
    static int[][] mapCopy(){
        int[][] nMap = new int[N+1][M+1];

        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                nMap[i][j] = map[i][j];
            }
        }
        return nMap;
    }

    static class Position{
        int n;
        int m;

        Position(int n, int m){
                this.n = n;
                this.m = m;
        }
    }


}

이건 꽤 할게 많은 것 같은데 정답률이 50%가 넘는다.

Scanner로 읽었을때 780ms 나와서 BufferdReader로 바꾸니 424ms로 줄었다.

맵이 64x64로 작긴 하지만, 샘플이 여러개니까 속도차이가 발생한다.