[BJ] 14502 연구소 Java

백준 14502 연구소

문제

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

14502번: 연구소

아이디어

• 벽을 3개 세워야하는데 DFS를 통해서 연구소 내에 벽 3개를 세울 수 있는 경우의 수에 대해서 모두 계산한다
• 벽을 3개 세웠으면 바이러스가 퍼져야하는데, BFS를 통해서 주변에 벽에 없는 곳으로 바이러스가 퍼질 것이다
• 매번 바이러스가 없는 영역을 구해서 최대값으로 갱신한다
• DFS + BFS를 사용해서 풀기

 

코드

import java.util.*;

class BJ14502 {
    static class Virus {
        int x, y;
        public Virus(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int n,m;
    static int answer = Integer.MIN_VALUE;
    static int[][] graph;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        graph = new int[n][m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

		// 벽이 처음에는 없음
        DFS(0);
        System.out.println(answer);

    }

    public static void DFS(int walls) {
        // 벽 3개를 다 세웠다면 바이러스 전파하고 넓이 구해봐야함
        if (walls == 3) {
            BFS();
            return;
        }

        // 벽 3개를 다 세우지 않았다면 3개를 세워봐야함
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (graph[i][j] == 0) {
                    graph[i][j] = 1;
                    DFS(walls+1);
                    graph[i][j] = 0; // 다른 경우도 생각해봐야하니 다시 0으로 되돌려
                }
            }
        }
    }

    public static void BFS() {
        Queue<Virus> q = new LinkedList<>();
        int[][] virusmap = new int[8][8];
        // 벽 세운 맵 복사하기
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                virusmap[i][j] = graph[i][j];
            }
        }

        // 바이러스가 있는 곳부터 BFS
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (virusmap[i][j] == 2) {
                    q.offer(new Virus(i,j));
                }
            }
        }

        while (!q.isEmpty()) {
            Virus cv = q.poll();
            for (int i=0; i<4; i++) {
                int nx = cv.x + dx[i];
                int ny = cv.y + dy[i];
                // 유효 범위이고, 바이러스가 없다면 바이러스가 퍼질것임
                if (nx>=0 && ny>=0 && nx<n && ny<m) {
                    if (virusmap[nx][ny] == 0) {
                        virusmap[nx][ny] = 2;
                        q.offer(new Virus(nx,ny));
                    }
                }
            }
        }
        // 매번 최대값 비교
        countArea(virusmap);
    }

    public static void countArea(int[][] virusmap) {
        int counter = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (virusmap[i][j] == 0) {
                    counter++;
                }
            }
        }
        answer = Math.max(answer, counter);
    }
}