[BOJ] 백준 14502 연구소 (JAVA)

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

14502번: 연구소

 

🔍 Solve

조합과 bfs를 사용해서 풀었습니다.

map 2차원 배열과 visited배열을 사용하는 것은 기존 bfs문제와 동일합니다.

이에 temp 배열에 조합으로 벽을 세우고, bfs로 불이 번지도록 하였습니다.

 

조합 코드에서는 

map배열을 탐색하여 map[i][j]가 0으로 빈 공간이라면 1로 변경하여 벽을 세워주고 count를 하나 증가하여 재귀를 탑니다.

재귀를 다 돌고나서는 다음 케이스에 영향이 가지 않도록 원래 상태로 map[i][j]를 0으로 변경해주어야 합니다.

조합을 다 돌고난 뒤, map배열을 temp배열에 깊은 복사 해주고, temp배열을 탐색합니다.

temp[i][j]에 바이러스가 있고(바이러스 위치 값 : 2), 아직 방문하지 않았다면 바이러스를 퍼뜨립니다.

 

마지막으로 safeCount() 함수를 통해 안전 영역의 크기를 세어주어, 가장 큰 값을 답으로 출력했습니다.

 

❗ Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int R, C;
    static int[][] map;
    static int[][] temp;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];
        temp = new int[R][C];

        for(int i=0;i<R;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        combination(0);
        System.out.println(max);

    }

    static void combination(int count){
        if(count==3){
            visited = new boolean[R][C];
            for(int i=0;i<R;i++){
                for(int j=0;j<C;j++){
                    temp[i][j] = map[i][j];  //map배열 복사
                }
            }

            for(int i=0;i<R;i++){
                for(int j=0;j<C;j++){
                    if(temp[i][j]==2){     //temp배열, 바이러스위치고
                        if(!visited[i][j]){  //아직 방문하지 X으면
                            bfs(i, j);  //바이러스 퍼트리기
                        }
                    }
                }
            }

            max = Math.max(max,safeCount());
            return;
        }

        //inductive part
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]==0){
                    //빈 공간에 벽세우기
                    map[i][j] = 1;
                    combination(count+1);
                    map[i][j] = 0;
                }
            }
        }
    }

    static void bfs(int r, int c){
        visited[r][c] = true;
        for(int d=0;d<4;d++){
            int nr = r+dr[d];
            int nc = c+dc[d];

            if(isIn(nr, nc) && temp[nr][nc]==0 && !visited[nr][nc]){
                temp[nr][nc] = 2; //바이러스
                bfs(nr, nc);
            }

        }
    }

    static int safeCount(){
        int count = 0;
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(temp[i][j]==0) count++;
            }
        }
        return count;
    }

    static boolean isIn(int r, int c){
        return r>=0 && c>=0 && r<R && c<C;
    }

}