[백준] 14502번 - 연구소

 

14502번: 연구소

 

 

연구소에 벽 3개를 세웠을 때 바이러스가 퍼지지 않은 안전 영역 크기의 최댓값을 구하는 문제이다.

 

우선 입력으로 주어지는 N x M 크기의 연구소를 이중 배열에 담는다. 요구하는 답을 찾기 위해서는 다음 일련의 과정을 거쳐 탐색을 실시해야한다.

 

i) 연구소 내부의 1x1 구획 공간 중 값 0을 갖는 방들 중 3개에 벽을 세운다.

ii) i)에서 벽 3개를 세웠을 때의 연구소에 대하여 바이러스가 퍼진 상황을 가정한다.

iii) ii)에서 연구소에 남은 빈칸의 수(값이 0)를 세어주고, 기존의 max 값과 비교하여 최댓값을 최신화시킨다.

 

처음 입력을 받을 때 값이 2 인 칸을 사전에 저장하여 ii) 과정 시 바이러스 시작 위치를 바로 알 수 있도록 하였다. 

i) 과정에 대해서는 깊이우선탐색(DFS)을 이용하여 벽을 세울 세개의 칸을 선택했다.

이 과정에서 DFS 함수를 재귀호출 했을 때 depth+1 이전에 탐색한 index 이후부터 탐색을 한다면 다음에 세울 벽에 대한 탐색이 보다 짧아지겠지만, 문제에서 주어진 연구소 한변의 최대 크기가 8로 작기 때문에 DFS 재귀 호출 시 언제나 연구소의 처음부터 탐색하는 것을 허용하였다.

DFS로 기존에 0이던 칸 3개를 1로 변경한 후, 과정 ii)에서 너비우선탐색(BFS)을 이용하여 바이러스가 퍼진 상황을 가정한다.

위 상황에서 countSafe 메서드를 사용하여 안전 영역의 갯수를 세어주고 최댓값을 최신화 해준다.

 

그리고 다시 i)을 반복하여 모든 빈 칸에 대하여 벽 3개를 세울 수 있는 상황에 대해 안전 영역의 수를 계산/비교한다.

 

 

 

전체 코드

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

public class Main {
    
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    static List<int[]> starting;
    static int[][] map;
    static int[][] copyMap;
    static int N, M, max;
    static Queue<int[]> que;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        starting = new ArrayList<>();
        StringTokenizer st = null;
        
        max = -1;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        copyMap = 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());
                if (map[i][j] == 2) starting.add(new int[] {i, j});
            }
        }
        
        
        
        dfs(0);
        
        System.out.println(max);
        
        br.close();
    }
    
    static void dfs (int depth) {
        
        // 연구소의 빈 칸 3개를 1로 변경한
        if (depth == 3) {
            bfs(); // bfs()로 연구소에 감염이 퍼진 상황을 가정
            max = Math.max(max, countSafe()); // 현재 상태에서 연구소 내부 안전 영역의 갯수를 비교
            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(depth + 1);
                    map[i][j] = 0;
                }
            }
        }
    }
    
    static void bfs () {
        
        que = new LinkedList<>();
        
        for (int i=0; i<N; i++) copyMap[i] = map[i].clone();
        
        for (int[] node : starting) que.offer(node.clone());
        
        // 현재 que에는 바이러스가 시작되는 좌표만이 들어가 있는 상태
        while (!que.isEmpty()) {
            
            int[] n = que.poll();
            
            for (int i=0; i<4; i++) {
                
                int ny = n[0] + dy[i];
                int nx = n[1] + dx[i];
                
                // (ny, nx)가 연구소 내부의 유효한 칸이고 빈 칸인 경우 바이러스가 퍼짐
                if (checkRange(ny, nx) && copyMap[ny][nx] == 0) { 
                    copyMap[ny][nx] = 2;
                    que.offer(new int[]{ny, nx});
                }
            }
        }
    }
    
    // 안전 영역의 갯수를 세는 함수
    static int countSafe () {
        
        int result = 0;
        
        for (int i=0; i<N; i++) 
            for (int j=0; j<M; j++) if (copyMap[i][j] == 0) result++;
        
        return result;
    }
    
    static boolean checkRange(int y, int x) {
        if (y >= 0 && x >= 0 && y < N && x < M) return true;
        return false;
    }
}