[JAVA] 백준 14502번 : 연구소

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

14502번: 연구소

---

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

public class Main {
    static int N, M, maxArea = 0; //세로, 가로
    static List<Pos> space = new ArrayList<>();
    static List<Pos> virus = new ArrayList<>();
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    private static class Pos {
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
        int x; int y;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[][] map = 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] == 0)
                    space.add(new Pos(i, j));
                else if(map[i][j] == 2)
                    virus.add(new Pos(i, j));
            }
        }
        setWall(map, -1, 0);
        System.out.println(maxArea);
    }

    private static void setWall(int[][] map, int idx, int cnt) {
        if(cnt == 3){
            maxArea = Math.max(maxArea, getMaxArea(map));
            return;
        }
        for (int i = idx + 1; i < space.size(); i++) {
            Pos p = space.get(i);
            map[p.x][p.y] = 1;
            setWall(map, i, cnt + 1);
            map[p.x][p.y] = 0;
        }
    }

    private static int getMaxArea(int[][] map) {
        int[][] tmpMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            tmpMap[i] = map[i].clone();
        }
        //바이러스 퍼뜨리기
        Queue<Pos> queue = new LinkedList<>(virus);
        while (!queue.isEmpty()) {
            Pos p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= M || tmpMap[nx][ny] != 0) continue;
                tmpMap[nx][ny] = 2;
                queue.add(new Pos(nx, ny));
            }
        }
        return calSafeZone(tmpMap);
    }

    private static int calSafeZone(int[][] tmpMap) {
        int area = 0;
        for (int i = 0; i < N; i++) {
            for (int n : tmpMap[i]) {
                if(n == 0) area++;
            }
        }
        return area;
    }
}

💡 완전 탐색, BFS

풀이

• 완전 탐색으로 벽을 세우고, BFS 방식으로 바이러스를 퍼트려 안전 구역의 크기를 구하는 방식

1. map 정보를 저장할 때, 빈 공간의 좌표와 바이러스의 좌표를 Pos 객체로 생성해 리스트에 저장함
2. 완전 탐색 메서드를 생성해 빈 공간 좌표리스트를 돌며 가능한 위치에 벽 3개를 세우는 경우의 수 시도
3. 벽 개수가 3개를 채운 경우, 해당 map을 복사해(tmpMap) BFS 방식으로 바이러스 퍼트림
4. BFS 탐색이 끝난 후 tmpMap에서 0의 개수를 셈 -> 안전구역 넓이 최댓값 갱신