연구소

📍 문제 설명

 

💡 접근

이코테에서 풀었던 문제다. 이코테에 있던 코드가 메모리 측면에서 5배 정도 좋게 나왔다.

이유는 벽을 세울 때 마다 값을 복사하는 배열을 생성해주어서였다..

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer,cnt, max, min, wall, result;
    static int[][] board, clone;
    static int[] visited = new int[100001];
    static int[] parent = new int[100001];
    static int[] ch,pm, combi;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static HashSet<String> set = new HashSet<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //0 빈칸, 1 벽, 2 바이러스 위치

        //일단 벽을 무조건 3개 채우고 나서 바이러스 전파시키기
        T.solution(0, 0, 0);
        System.out.println(result);
    }

    private void solution(int x, int y, int wall) {
        //벽을 3개 세웠으면 2인 지점에 대해서 상하좌우로 바이러스 전파
        if(wall == 3) {
            clone = new int[n][m];
            //배열값 복사
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    clone[i][j] = board[i][j];
                }
            }
            //바이러스 전파
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(clone[i][j] == 2) {
                        virusSpread(i, j, clone);
                    }
                }
            }
            //안전 영역 계산
            result = Math.max(result, getScore());
        }
        //벽 세우기
        else {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(board[i][j] == 0) {
                        board[i][j] = 1;
                        solution(0,0, wall+1);
                        board[i][j] = 0;
                    }
                }
            }
        }
    }

    private int getScore() {
        int score = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (clone[i][j] == 0) {
                    score += 1;
                }
            }
        }
        return score;
    }

    private void virusSpread(int x, int y, int[][] clone) {
        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 && clone[nx][ny] == 0) {
                clone[nx][ny] = 2;
                virusSpread(nx, ny, clone);
            }
        }
    }
}