[BOJ] 백준 14502 연구소

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

14502번: 연구소

 

---

 

풀이 방법

1. 벽을 3개를 세울 수가 있는데 어디에 세우느냐에 따라 바이러스가 퍼지는 영역이 달라지게 된다. 따라서 벽을 세울 수 있는 모든 경우를 전부 탐색해야 한다.
2. 초기에 입력받을 배열과 벽을 세울 경우를 탐색하기 위한 배열, 벽을 세웠을 때 바이러스가 퍼졌을 경우의 배열 이렇게 세 가지의 배열이 필요하다.
3. 바이러스가 퍼졌을 경우, 바이러스가 퍼지지 않은 영역인 안전 영역 즉 값이 0인 영역을 bfs를 사용해서 count를 한다.
4. 벽을 세울 때마다 안전 영역의 수가 달라지므로 모든 경우의 수를 count 해서 최댓값을 도출한다.

 

다음은 Java로 작성한 코드이다.

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

public class B14502 {
    private static final int [] dx = { -1, 1, 0, 0 }; // 상하좌우
    private static final int [] dy = { 0, 0, -1, 1 };
    private static int n, m;
    private static int [][] map;
    private static int answer = Integer.MIN_VALUE;

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

        String [] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        int[][] inputMap = new int[n][m];
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                inputMap[i][j] = map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (inputMap[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(1);
                    map[i][j] = 0;
                }
            }
        }

        System.out.println(answer);
    }

    private static void dfs(int count) {
        if (count == 3) {
            bfs();
            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(count+1);
                    map[i][j] = 0;
                }
            }
        }
    }

    private static void bfs() {
        int [][] resultMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                resultMap[i][j] = map[i][j];
            }
        }

        Queue<int []> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (resultMap[i][j] == 2)
                    q.offer(new int[]{i, j});
            }
        }

        while (!q.isEmpty()) {
            int curX = q.peek()[0];
            int curY = q.peek()[1];
            q.poll();

            for (int dir = 0; dir < 4; dir++) {
                int nx = curX + dx[dir];
                int ny = curY + dy[dir];

                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (resultMap[nx][ny] == 0) {
                        resultMap[nx][ny] = 2;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        countSafeArea(resultMap);
    }

    private static void countSafeArea(int [][] resultMap) {
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (resultMap[i][j] == 0)
                    count++;
            }
        }

        answer = Math.max(count, answer);
    }
}