[Algorithm] 연구소

풀이

 

벽을 세운 개수가 3개가 될 때마다 임시 맵에 바이러스가 퍼진 결과, 그리고 안전한 공간을 계산하도록 한다.

안전한 공간의 수는 최대값으로 갱신한다.

바이러스가 퍼지는 공간은 DFS로 면적을 포함해가면 된다.

    public 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 (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (tmp[nx][ny] == 0) {
                    tmp[nx][ny] = 2;
                    virus(nx, ny);
                }
            }
        }
    }

안전한 공간은 바이러스가 퍼지고 난 후에 맵에서 안전한 공간의 갯수를 파악한다.

    public static int getSafe() {
        int safe = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tmp[i][j] == 0) {
                    safe++;
                }
            }
        }
        return safe;
    }

벽을 세우는 방식은 재귀 호출을 통해 맵에서 모든 경우의 수를 세워볼 수 있도록 한다.

처음에 0,0 0,1 0,2 -> 0,0 0,1 0,3 -> ... -> 0,0 0,1 n,m -> 0,0 0,2 0,3 -> ...

이렇게 모든 경우를 확인할 수 있다. 그 때 벽의 개수가 3개일 때마다 바이러스의 퍼짐 정도와 안전한 공간을 계산하면 된다.

    public static void dfs(int cnt) {
        // 벽 3개 건설된 경우
        if (cnt == 3) {
            // 바이러스 퍼짐 정도와 안전공간 개수 확인
        }
        // 벽 건설
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    cnt++;
                    dfs(cnt);
                    map[i][j] = 0;
                    cnt--;
                }
            }
        }
    }

전체 소스코드

import java.util.*;

public class Main {
    public static int n, m;
    public static int[][] map = new int[8][8];
    // 바이러스 전파 상황 저장할 맵
    public static int[][] tmp = new int[8][8];
    
    public static int safeZone = 0;
    
    // 상 좌 하 우
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};

    public 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 (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (tmp[nx][ny] == 0) {
                    tmp[nx][ny] = 2;
                    virus(nx, ny);
                }
            }
        }
    }

    public static int getSafe() {
        int safe = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tmp[i][j] == 0) {
                    safe++;
                }
            }
        }
        return safe;
    }

    public static void dfs(int cnt) {
        // 벽 3개 건설된 경우
        if (cnt == 3) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    tmp[i][j] = map[i][j];
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (tmp[i][j] == 2) {
                        virus(i, j);
                    }
                }
            }
            safeZone = Math.max(safeZone, getSafe());
            return;
        }
        // 벽 건설
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    cnt++;
                    dfs(cnt);
                    map[i][j] = 0;
                    cnt--;
                }
            }
        }
    }

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        sc.close();

        dfs(0);

        System.out.println(safeZone);

    } // end main method
}