2023-04-03 BOJ 14502

문제 풀이 방식

• 바이러스 최대 넓이 : BFS
• 못나가게 벽세우기 : DFS

문제 풀이 (Java)

import java.io.*;  
import java.util.*;  
  
class virusPoint {  
    int row;  
    int col;  
  
    public virusPoint(int row, int col) {  
        super();  
        this.row = row;  
        this.col = col;  
    }  
  
}  
  
public class boj14502 {  
  
    static int N, M, max;   
    static int[][] map;  
    static int[][] wall;   
    static int[] dy = { -1, 1, 0, 0 };   
    static int[] dx = { 0, 0, -1, 1 };  
    static ArrayList<virusPoint> virusList;  
  
    public static boolean isValid(int row, int col) {  
        if (row < 0 || row >= N || col < 0 || col >= M)  
            return false;  
        return true;  
    }  
  
    public static int[][] copy(int [][] arr) {  
  
        int[][] copy = new int[N][M];  
  
        for (int i = 0; i < N; i++) {  
            for (int j = 0; j < M; j++) {  
                copy[i][j] = arr[i][j];  
            }  
        }  
        return copy;  
    }  
  
    public static void makeWall(int depth) {  
  
        if (depth == 3) {  
            spreadVirus();  
            return;  
        }  
  
        for (int i = 0; i < N; i++) {  
            for (int j = 0; j < M; j++) {  
                if (wall[i][j] == 0) { // 빈칸인 경우  
                    wall[i][j] = 1; // 벽 건설  
                    makeWall(depth + 1);  
                    wall[i][j] = 0; // 다음 경우의 수를 위해 복구  
                }  
            }  
        }  
    }  
  
    // 벽을 세웠을 경우, virus 전염  
    private static void spreadVirus() {  
  
        int[][] copyWall = copy(wall); // 바이러스를 확장 시킬 복사 맵  
  
        Queue<virusPoint> vq = new LinkedList<virusPoint>();   
        for (int i = 0; i < virusList.size(); i++) {  
            vq.offer(new virusPoint(virusList.get(i).row, virusList.get(i).col));  
        }  
  
        while (!vq.isEmpty()) {  
            int row = vq.peek().row;  
            int col = vq.poll().col;  
  
            for (int k = 0; k < 4; k++) {  
                int nextRow = row + dy[k];  
                int nextCol = col + dx[k];  
  
                if (isValid(nextRow, nextCol) && copyWall[nextRow][nextCol] == 0) {  
                    copyWall[nextRow][nextCol] = 2;  
                    vq.offer(new virusPoint(nextRow, nextCol));  
                }  
  
            }  
        } // end of spread  
  
        int sc = countSafe(copyWall);  
        max = Math.max(max, sc);  
    }  
  
    public static int countSafe(int[][] copyWall) {  
        int sc = 0;  
        for (int i = 0; i < N; i++) {  
            for (int j = 0; j < M; j++) {  
                if (copyWall[i][j] == 0) {  
                    sc++;  
                }  
            }  
        }  
        return sc;  
    }  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = null;  
  
        st = new StringTokenizer(br.readLine());  
        virusList = new ArrayList<virusPoint>();  
        N = Integer.parseInt(st.nextToken());  
        M = Integer.parseInt(st.nextToken());  
        map = new int[N][M];  
        max = 0;  
  
        for (int i = 0; i < N; i++) {  
            st = new StringTokenizer(br.readLine());  
            for (int j = 0; j < M; j++) {  
                map[i][j] = Integer.parseInt(st.nextToken());  
                // 입력을 받으면서 바이러스 초기값 탐색  
                if (map[i][j] == 2) {  
                    virusList.add(new virusPoint(i, j));  
                }  
            }  
        } // end of input  
  
        // 3개의 벽을 세우기 위한 copy map        wall = copy(map);  
  
        makeWall(0);  
  
        System.out.println(max);  
    }   
  
}