14502 java

최대의 공간을 확보하기 위해 벽이 3개를 설치 => 모든 경우를 DFS()로 탐색 ,벽 3개 설치

DFS를 통해 벽 3개 설치되면 바이러스부분에서 BFS를 한다

큐를 통해 바이러스 위치를 저장하고 바이러스에서 BFS 

 

import java.util.*;
import java.io.*;
 
public class Main {
    
    static final int dx[] = {0,0,1,-1};
    static final int dy[] = {1,-1,0,0};
    static int n,m;
    static int map[][];
    static int maxValue = -1;
    
 
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        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());
            }
        }
 
        dfs(0);
        System.out.print(maxValue);
        
        
        
    }
    
    static void dfs(int count) {
        if(count == 3) {
            bfs();
            return;
        }
        for(int i=0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(count+1);
                    map[i][j] = 0;
                }
            }
        }
    }
    
    static void bfs() {
        Queue<Node> q = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(map[i][j] == 2) {
                    q.add(new Node(i,j));
                }
            }
        }
        int copyMap[][] = new int[n][m];
        for(int i =0; i<n; i++) {
            copyMap[i] = map[i].clone();
        }
        while(!q.isEmpty()) {
            Node now = q.poll();
            int x = now.x;
            int y = now.y;
            
            for(int k=0; k<4; k++) {
                int nx = x +dx[k];
                int ny = y + dy[k];
                
                if(nx >=0 && nx <n && ny >=0 && ny <m) {
                    if(copyMap[nx][ny] == 0) {
                        q.add(new Node(nx, ny));
                        copyMap[nx][ny] = 2;
                    }
                }
            }
        }
        zone(copyMap);
    }
    
    static void zone(int[][] copyMap) {
        int safe  =0;
        for(int i=0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(copyMap[i][j] == 0) {
                    safe++;
                }
            }
        }
        if(maxValue < safe) {
            maxValue = safe;
        }
    }
    
    static class Node{
        int x;
        int y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
 
}
 

 

https://www.acmicpc.net/problem/14502

14502번: 연구소