<Algorithm> 45. 14502번 연구소

1. 14502번 연구소

• BFS, DFS 중급 문제, DFS를 사용하여 벽을 세울 경우 백트레킹이 들어가야 한다.

• 처음에 for문을 이용하여 벽을 세우려고 했지만 4중 for문에 또 DFS , 안전영역 체크 까지 for문이 많이 중첩되어 문제가 발생했다,

• 벽을 세울때 DFS와 백트래킹을 이용하여 벽을 세우고 -> DFS (벽 3개가 될떄지 ) - > 벽 3개가 되면 BFS를 호출하고 끝나면 백트래킹

• DFS로 영역을 확장하는 것 이외에 벽세우기 같은 순차적으로 반복했을 때도 사용 가능하다는 것을 알게된 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static boolean[][] visited;
    static int max = 0;
    static ArrayList<Coordinate> virus = new ArrayList<>();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][M];
        
        for(int i = 0; i < N; i ++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 2) { // 바이러스가 있는 위치 확인
                    virus.add(new Coordinate(i, j));
                }
            }
        }
        dfs(arr, N, M, 0);
        
       System.out.println(max);
        
    }
        
    
    public static void dfs(int arr[][], int N, int M, int wall) {
        // 3개의 벽을 세우기 위한  dfs
        
        if(wall == 3) {
            visited = new boolean[N][M]; // 바이러스 영역 표시
            bfs(arr, N, M); // 바이러스 확장
            return;
        }
        
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < M; j ++) {
                if(arr[i][j] == 0) {
                    arr[i][j] = 1; // 벽을 하나 세운다
                    dfs(arr, N, M, wall + 1); // 3개 세울떄까지 반복한다. 
                    arr[i][j] = 0; // 백트레킹
                }
            }
        }
    }
    
    public static void bfs(int arr[][], int N, int M) {
        // 벽에 따른 바이러스 확장을 위한 BFS
        
        Queue<Coordinate> queue = new LinkedList<>();
        
        for(Coordinate loc : virus) {
            queue.add(new Coordinate(loc.x, loc.y));
        } // 최초 바이러스가 담겨있는 것을 큐에 다 담는다
        
        int dx [] = {0, 0, 1, -1};
        int dy [] = {1, -1, 0 , 0};
        
        while(!queue.isEmpty()) {
            Coordinate loc = queue.remove();
            int x = loc.x;
            int y = loc.y;
            
            for(int i = 0; i < dx.length; i++) {
                   int nx = x + dx[i];    
                   int ny = y + dy[i];
                   
                   if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && arr[nx][ny] == 0) {
                           // 바이러스 영역 확장
                       queue.add(new Coordinate(nx, ny));
                           visited[nx][ny] = true;
                   }
            }
        }
        
        saftyArea(arr, N, M);// 안전영역 개수 확인
        
    }
    
    public static void saftyArea(int [][] arr, int N, int M) {
        int count = 0;
        
        for(int i = 0; i < N; i ++ ) {
            for(int j = 0; j < M ; j ++) {
                if( !visited[i][j] && arr[i][j] == 0 ) {
                    count++; 
                }
            }
        }
        max = Math.max(max, count);
        
    }
}
 
class Coordinate{
    int x, y;
 
    public Coordinate(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
}