[JAVA/DFS,BFS] 백준 14502 연구소

1. 문제

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

14502번: 연구소

 

2. 풀이

벽을 세울 위치를 선택할 때 DFS, 바이러스가 퍼지는 과정은 BFS를 이용해 풀이한다.

• 입력을 받을 때, 바이러스가 있는 좌표(값이 2인 부분)은 따로 저장해둔다.
• DFS를 이용해 벽을 세운다. 재귀함수를 이용해 DFS를 구현한다.
  • map 중 벽을 세울 수 있는 부분(map[i][j] == 0)에 벽을 세운다.(map[i][j] = 1)
  • 3개의 벽을 모두 세울때까지 재귀함수를 호출해 이 과정을 반복한다.
  • 재귀함수 호출 후, 다른 위치에도 벽을 세울 수 있도록 벽을 없음 처리 한다(map[i][j] = 0).
• 3개의 벽이 모두 세워지면, 벽이 세워졌을 때 바이러스를 퍼트린다. 이 때, BFS를 사용한다.
  • map을 깊은 복사한 cMap을 만들어, 바이러스가 퍼진 모습을 cMap 위에 표시한다.
  • 바이러스가 있는 위치를 모두 큐에 넣은 후, 큐가 빌때까지 BFS를 해 바이러스를 퍼트린다.
  • 큐가 비면 안전구역의 갯수를 구한다.(getSafeArea())

 

3. 코드

 

import java.util.*;
import java.io.*;

class Main{
    
    static int n, m;
    static int[][] map;
    static ArrayList<int[]> virusPoints; // 바이러스의 좌표 저장
    static int wallCnt = 3; // 총 세울 수 있는 벽의 수
    static int max = 0; // 가장 큰 safeArea 크기
    static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    
    // 2차원 배열 깊은 복사
    public static int[][] copyMap(){
        int[][] cMap = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cMap[i][j] = map[i][j];
            }
        }
        return cMap;
    }
    
    // 바이러스 퍼짐 처리
    public static int spreadVirus() {
        Queue<int[]> q = new LinkedList<>();
        int[][] cMap = copyMap();
        
        for(int i = 0; i < virusPoints.size(); i++) {
            q.offer(virusPoints.get(i));
        }
        
        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int d = 0; d < 4; d++) {
                int newX = now[0] + dir[d][0];
                int newY = now[1] + dir[d][1];
                if(newX < 0 || newY < 0 || newX >= n || newY >= m) continue;
                
                if(cMap[newX][newY] == 0) { // 바이러스가 퍼질 수 있는 경우
                    cMap[newX][newY] = 2; 
                    q.offer(new int[]{newX, newY});
                }
            }
        }
        
        return getSafeArea(cMap);
    }
    
    // 안전한 구역의 갯수를 리턴
    public static int getSafeArea(int[][] map) {
        
        int area = 0;
        
        for(int i = 0; i < n; i++) 
            for(int j = 0; j < m; j++) 
                if(map[i][j] == 0) area++;
        
        return area;
    }
    
    // dfs를 이용해 벽을 세움
    public static void makeWall(int wall) {
        
        if(wall == wallCnt) { // 벽을 모두 세운 경우
            max = Math.max(max, spreadVirus());
            return;
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 0) {
                    map[i][j] = 1;
                    makeWall(wall + 1);
                    map[i][j] = 0; 
                }
            }
        }
        
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        map = new int[n][m];

        virusPoints = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            String[] input2 = br.readLine().split(" ");
            for(int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(input2[j]);
                if(map[i][j] == 2) virusPoints.add(new int[] {i,j});
            }
        }
        
        makeWall(0);
        
        System.out.println(max);
    }
}