[백준 14502, Java] 연구소

문제

www.acmicpc.net/problem/14502

14502번: 연구소

 

접근

1. 문제를 3개로 나누었다. 벽세우기/ 바이러스 확산/ 안전지역 count

2. 벽세우기 문제는 NK과 K(1) 과 같다. map을 순회하며 셀이 빈칸인 곳에 벽을 세운다.

3. 바이러스 확산은 바이러스인 셀을 기준으로 상하좌우 셀 중 빈칸인 곳에 바이러스를 만들고, 다시 이 바이러스 셀을 기준으로 상하좌우를 탐색한다. BFS 를 이용한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        virusMap = new int[N][M];

        for(int r=0;r<N ;r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<M; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        buildWall(0, 0, 0);
        bw.write(String.valueOf(maxCount));
        bw.flush();


    }
    public static final int BLANK = 0;
    public static final int WALL = 1;
    public static final int VIRUS =2;

    public static int N;
    public static int M;
    public static int[][] map;
    public static int[][] virusMap;
    public static Queue<Pair> virusQueue;
    public static int maxCount =-1;

    public static class Pair{
        int x;
        int y;
        Pair(int x, int y){
            this.x = x;
            this.y= y;
        }
    }

    public static int[] directionX = {0,1,0,-1};
    public static int[] directionY = {1,0,-1,0};

    public static void buildWall(int row, int column, int count){
        if(count>=3){
            setVirusMap();
            spreadVirus();
        }
        else{
            for(int r =row; r<N; r++){
                for(int c=(r==row?column:0);c<M;c++){
                    if(map[r][c] ==BLANK){
                        map[r][c] = WALL;
                        buildWall(r,c,count+1);
                        map[r][c] = BLANK;
                    }
                }
            }
        }
    }
    public static void spreadVirus(){
        while(!virusQueue.isEmpty()){
            Pair currentVirus = virusQueue.remove();
            int x = currentVirus.x;
            int y = currentVirus.y;

            for(int d=0;d<4;d++){
                int dx = x+directionX[d];
                int dy = y+directionY[d];

                if(dx>=0 && dx<N && dy>=0 && dy<M && virusMap[dx][dy]==BLANK){
                    virusMap[dx][dy] = VIRUS;
                    virusQueue.add(new Pair(dx, dy));
                }
            }
        }
        countSafeZone();
    }

    public static void countSafeZone(){
        int count =0;
        for(int r= 0;r<N; r++){
            for(int c=0; c<M;c++){
                if(virusMap[r][c] == BLANK){
                    count++;
                }
            }
        }
        maxCount = Math.max(maxCount, count);
    }
    public static void setVirusMap(){
        virusQueue = new LinkedList<>();
        for(int r= 0; r<N; r++){
            for(int c= 0; c<M;c++){
                virusMap[r][c] = map[r][c];

                if(virusMap[r][c] ==VIRUS){
                    Pair pair = new Pair(r, c);
                    virusQueue.add(pair);
                }
            }
        }
    }
    public static void printMap(int[][] map){
        for(int r= 0; r<N; r++){
            for(int c=0; c<M; c++){
                System.out.print(map[r][c]+" ");
            }
            System.out.println();
        }
    }
}