[백준] 14502번 연구소

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q14502.java

연구소에서 바이러스가 퍼져나가는 것을 막기위해 벽을 세우려고 한다. 벽은 꼭 3개를 세워야한다.
이 때, 안전 구역의 최대값을 구하여라.

처음 생각

우선 접근하는 방식은 SW Expert의 모의 문제인 벽돌 깨기와 비슷한다. [모의 SW 역량테스트] 벽돌 깨기 이 문제와 마찬가지로 범위의 제한이 아주적다. 벽은 3개이고 맵의 크기도 최대 [8][8]이다. 따라서 완전 탐색을 이용해서 벽 3개를 세울수 있는 모든 조건을 구해서 안전 구역을 구해주었다.

▶ 시간에대해 간단히 계산을 해보면 최대 [8][8]이므로 맵의 크기는 최대 64가 된다. 이중 3개를 선택하는 것이므로 가장 크게 따져도 64x63x62 = 249,984 이며, 새로운 탐색시마다 [8][8] 배열을 초기화 시켜도 2초라는 제한 시간 안에는 아주 거뜬한다.

▶ 실제로는 맵 안에 바이러스나 벽들이 배치되어 있으므로, 최대를 따져도 저거보다는 덜 걸릴 것이다.

다음 생각

다음으로 벽을 세우기 위해서 장소를 택할 때, 3개의 벽을 배치하는 장소가 1차가아니고 2차 배열에서 따져주어야하므로 비트 마스크보다는 재귀를 이용한 DFS 탐색으로 구해주는 것이 편한다.

▶ 이전 문제인 [백준] 15684번 사다리 조작 에서와 같이 2차 배열의 DFS 탐색으로 모든 조합을 구해주었다. 벽을 카운트 하는 변수인 cnt가 3이되면 check()를 해주었다.

다다음 생각

check() 메소드는 해당 조합으로 벽 3개를 설치했을 때, BFS를 이용해서 바이러스를 실제로 퍼트려보는 것이다. 맵이 크지 않으므로 케이스마다 실제로 퍼트려주었다.

▶ 바이러스의 초기 위치는 매번 사용되므로 입력을 받을 때, 미리 List에 넣어놓았다.

▶ 바이러스를 다 퍼트리고 안전 구역을 카운트 해도 상관은 없겠지만 조금이라도 빨리 돌리기위해서 입력 받을 때, 안전 구역을 다 카운트 한 후, 바이러스가 한 번 퍼질 때마다 이 개수를 -1 시켜주었다.

다다다음 생각

위에서 카운트한 안전 구역의 개수는 벽의 위치 3개를 빼놓고 카운트 했으므로, 실제 출력할 때는 -3을 해준 값을 출력하였다.

방안

1) DFS와 BFS를 다 사용하는 벽돌 깨기 문제와 비슷한 문제였다. 물론 BFS를 사용하지 않고 DFS를 사용해도 되지만 퍼트리는 것이 목적이므로 BFS가 더 알맞다.

2) 입력이 적어 Scanner를 통해 입력을 받았다.

package baekjoon.swtest;
 
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
public class Q14502 {
    static int n,m;
    static int[][] arr,copy;
    static List<Pair> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 세로 크기
        m = sc.nextInt(); // 가로 크기
        arr = new int[n][m];
        copy = new int[n][m];
        visited = new boolean[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                arr[i][j] = sc.nextInt();
                // 바이러스 장소 넣어주기
                if(arr[i][j]==2) list.add(new Pair(i, j));
                else if(arr[i][j]==0) safeCnt++;
            }
        }
        // 결과값 초기화
        result = 0;
        solve(0,0,0);
        // 벽을 세우는데 3개를 사용했기 때문에 -3을 해준다.
        System.out.println(result-3);
    }
    
    private static void solve(int x,int y,int cnt) {
        // 벽 3개를 세웠으면 체크하러 가기
        if(cnt==3) {
            check();
            return;
        }
        
        // y index가 범위를 넘겼으면 x를 +1시켜 다음줄로.
        if(y>=m) {
            solve(x+1,0,cnt);
            return;
        }
        
        // x index가 범위를 넘겼으면 끝.
        if(x>=n) return;
        
        
        // 맵에서 해당 장소가 0 즉, 벽을 세울 수 있다면 세워주자.
        if(arr[x][y]==0) {
            arr[x][y] = 1;
            solve(x,y+1,cnt+1);
            arr[x][y] = 0;
        }
        // 세울 수 없다면 그냥 다음 index로 넘겨주자.
        solve(x,y+1,cnt);
    }
    
    static int result,safeCnt;
    static boolean[][] visited;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void check() {
        init(); // 검사전 초기화
        Queue<Pair> queue = new LinkedList<>();
        int safe = safeCnt;
        // 바이러스 queue에 넣어주기
        for(Pair t:list) {
            visited[t.x][t.y] = true;
            queue.add(t);
        }
        // 바이러스 퍼트리기
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            for(int i=0;i<4;i++) {
                int tx = t.x+dir[i][0];
                int ty = t.y+dir[i][1];
                if(tx<0 || ty<0 || tx>=n || ty>=m) continue;
                if(visited[tx][ty]) continue;
                if(arr[tx][ty]==0) {
                    visited[tx][ty] = true;
                    queue.add(new Pair(tx, ty));
                    safe--; // 안전 범위 개수 감소
                }
            }
        }
        // safe(이번 케이스의 안전 범위 개수)와 전체 값 비교
        result = Math.max(result, safe);
    }
    
    // 검사하기전 맵 & 방문 초기화
    private static void init() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                copy[i][j] = arr[i][j];
                visited[i][j] = false;
            }
        }
    }
    
    static class Pair{
        private int x,y;
        Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}