16.연구소

📍 문제 설명

 

💡 접근

1.빈 공간에 벽설치

2.벽이 3개 설치 됐을 때 2인 지점 바이러스 전파

3.남아 있는 안전 영역 크기 중 최댓값 저장

 

2.에서 기존 배열이 아닌 기존 배열을 저장하는 임시 배열을 쓴 이유는

상하좌우를 탐색해나가면서 종착점에 대한 기준이 있어야 그 종착점에서의 안전 영역 크기를 구한 후 배열을 원래의 값으로 변경시키는데 없기 때문에 쓰고나서 버릴 배열을 사용했다.

👩‍💻 코드

import java.util.*;

public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int n, m, result;
    static int[][] map, temp;

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); //지도 세로 길이
        m = kb.nextInt(); //지도 가로 길이
        map = new int[n][m];
        temp = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                map[i][j] = kb.nextInt();
            }
        }

        //일단 빈 칸인 부분에 3번 까지 벽을 세운다.
        //바이러스인 칸 상하좌우가 벽이 아니면 바이러스를 전파시킨다.
        //남아있는 안전영역크기의 값을 구한다.

        //넘어가는 값은 벽을 세운 횟수,
        dfs(0);
        System.out.println(result);


    }

    //벽을 설치하고 안전 영역 계산
    private static void dfs(int count) {
        //벽 설치 다 됐으면 바이러스 전파
        if(count == 3) {
            //바이러스 전파할 때 사용할 배열
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    temp[i][j] = map[i][j];
                }
            }
            //바이러스 전파를 위해 해당 좌표로 virus 전파
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(temp[i][j] == 2) {
                        virus(i,j);
                    }
                }
            }
            result = Math.max(result, getScore());
        }
        //빈 공간에 벽 설치(0인 공간에 모든 경우의 수를 고려하여 벽 3개 설치)
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 0) {
                        count++;
                        map[i][j] = 1;
                        dfs(count);
                        //벽설치 완료됐을 때 다른 벽들 확인을 위해 다시 원래대로
                        count--;
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    // 현재 맵에서 안전 영역의 크기 계산하는 메서드
    public static int getScore() {
        int score = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (temp[i][j] == 0) {
                    score += 1;
                }
            }
        }
        return score;
    }

    //해당 좌표를 가진 바이러스를 상하좌우로 퍼지게 하기
    private static void virus(int x, int y) {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            //상하좌우로 퍼질 수 있으면 다 퍼트리기
            if(nx >= 0 && ny >= 0 && nx < n && ny < m && temp[nx][ny] == 0) {
                temp[nx][ny] = 2;
                //전파된 좌표에 대해 다시 바이러스 전파
                virus(nx, ny);
            }

        }
    }
}